链表的就地操作
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 / 常见坑
i.
没保存 next 就把后续链表丢了。
如果在保存原本的
curr.next 之前就翻转 curr.next ← prev, 后面那一截就被切断了。保存这一步不可省 —— 这正是要用三个指针的全部原因。ii.
返回值搞错。
循环结束时,
curr 是 null,prev 才是新的头节点。 返回 curr 会在非空链表上得到 null —— 一个常见的低级错误。iii.
没处理空链表。
当
head = null 时循环不会执行,prev 保持为 null。 这是正确的 —— 但前提是循环体一次也不进入。务必显式验证空链表的情形; 一旦在判空之前就先访问 curr.next,很容易写出空指针解引用。05 / 去 LeetCode 上练习
四道题。前两道是不同形态下的反转。第三道是经典的合并。 第四道则是指针腾挪真正担当主角的地方。