链表的就地操作
01 / 一句话本质
要原地改写一条链表,就用三个指针 prev、curr、next 遍历 —— 翻转前先保存,翻转后再前进,后续链表在每一步都仍然可达。
题目原地反转一条单向链表输入[1 → 2 → 3 → 4 → 5]
三个指针:prev 指向 null,curr 指向头节点。next 将在每一步保存原本的指针。
步
0 / 16
prev
null
curr
1 [0]
动作
init
0 / 16
02 / 模式骨架
# 反转一条单链表prev ← nullcurr ← headwhile curr ≠ null:next ← curr.next // 1. 保存curr.next ← prev // 2. 翻转prev ← curr // 3. 推进 prevcurr ← next // 4. 推进 currreturn prev // 新的头节点
03 / 什么时候用这个模式
"原地 / O(1) 空间"
约束禁止再开一条新链表 —— 必须重连现有节点。 这正是多指针操作的用武之地。
"反转 / 重排"
你改变的是链表的结构,而不是值。值不变,变的是
.next 指向。"子段 / 区间"
反转的是两个位置之间的一段,而不是整条链表。算法相同,边界处多了一步缝合。
"合并 / 交错"
把两条链表并成一条,交替或有序。常用"哑节点"技巧简化首尾的边界处理 —— 最后从
dummy.next 接出结果。04 / 常见坑
没保存 next 就把后续链表丢了。
如果在保存原本的
curr.next 之前就翻转 curr.next ← prev, 后面那一截就被切断了。保存这一步不可省 —— 这正是要用三个指针的全部原因。返回值搞错。
循环结束时,
curr 是 null,prev 才是新的头节点。 返回 curr 会在非空链表上得到 null —— 一个常见的低级错误。没处理空链表。
当
head = null 时循环不会执行,prev 保持为 null。 这是正确的 —— 但前提是循环体一次也不进入。务必显式验证空链表的情形; 一旦在判空之前就先访问 curr.next,很容易写出空指针解引用。05 / 去 LeetCode 上练习
简单9
01Merge Two Sorted Lists— LC 21→02Remove Duplicates from Sorted List— LC 83→03Linked List Cycle— LC 141→04Intersection of Two Linked Lists— LC 160→05Remove Linked List Elements— LC 203→06Reverse Linked List— LC 206→07Palindrome Linked List— LC 234→08Middle of the Linked List— LC 876→09Convert Binary Number in a Linked List to Integer— LC 1290→
中等33
01Add Two Numbers— LC 2→02Remove Nth Node From End of List— LC 19→03Swap Nodes in Pairs— LC 24→04Rotate List— LC 61→05Remove Duplicates from Sorted List II— LC 82→06Partition List— LC 86→07Reverse Linked List II— LC 92→08Convert Sorted List to Binary Search Tree— LC 109→09Flatten Binary Tree to Linked List— LC 114→10Populating Next Right Pointers in Each Node— LC 116→11Populating Next Right Pointers in Each Node II— LC 117→12Copy List with Random Pointer— LC 138→13Linked List Cycle II— LC 142→14Reorder List— LC 143→15LRU Cache— LC 146→16Sort List— LC 148→17Delete Node in a Linked List— LC 237→18Odd Even Linked List— LC 328→19Plus One Linked List— LC 369→20Linked List Random Node— LC 382→21Flatten a Multilevel Doubly Linked List— LC 430→22Add Two Numbers II— LC 445→23Design Linked List— LC 707→24Split Linked List in Parts— LC 725→25Next Greater Node In Linked List— LC 1019→26Remove Zero Sum Consecutive Nodes from Linked List— LC 1171→27Print Immutable Linked List in Reverse— LC 1265→28Linked List in Binary Tree— LC 1367→29Merge In Between Linked Lists— LC 1669→30Swapping Nodes in a Linked List— LC 1721→31Reverse Nodes in Even Length Groups— LC 2074→32Delete the Middle Node of a Linked List— LC 2095→33Maximum Twin Sum of a Linked List— LC 2130→