链表有限、无环、单向链接;位置从 1 开始且有效。使用教学正文的算法和 dummy 节点约定。
复习路线。 重写链接前确定 before、first 和 after。追踪保存的下一节点引用及反转前缀,只在循环结束后重新连接前驱。
检查清单。 修改 curr.next 前先保存它。把 prev 初始化为 after。若 ,返回 dummy 更新后的 next;若 ,after 为空。必须保留原节点和后缀。
1. 追踪中间片段
练习
(对于 ,反转第 3 至第 5 个位置。给出 before、after 及每次循环迭代后的 prev 和 curr,并写出返回的链。)
核心
提示(1)
先找出
before和after,并把prev起初设为after。
解答(3)
- 1
找出边界节点
before=B,after=F。初始prev=F、curr=C。 - 2
执行三次迭代
关键一步
第一次迭代后
prev=C、curr=D,链为 ;第二次后prev=D、curr=E,链为 ;第三次后prev=E、curr=F,链为 。依据: 每次迭代都在改写
curr.next之前先保存它。 - 3
重新连接前驱
由于
curr == after,停止并令 。返回链为 。
2. 头指针发生变化
练习
(链表含不同节点,值为 。反转第 1 至第 3 个位置。指出 dummy 最终的 next、旧头最终的后继和返回链表。如果调用者从未收到返回的头,为什么仅对局部变量 head 赋值不够?)
核心
提示(1)
时,哪个节点担当
before的角色?
解答(3)
- 1
找出边界节点
before是 dummy,after是值为 4 的节点。反转片段 得到 。 - 2
读出最终链接
dummy 最终的
next是节点 9;旧头 7 现在指向 4。返回 dummy 的next。 - 3
解释为何需要返回的头
若函数只改变其局部
head变量,这个赋值本身不会改变调用者独立的头变量;调用者必须使用返回的头,或明确传入对其头变量的可修改引用。节点链接已经改变,所以保留旧头只会看到从 7 开始的后缀。
快速检查
(对 ,、,before、after 及返回的链各是什么?)
片段延伸到链表末端时,after 是什么?
解答 · 答案
before 是 dummy,after 为空,因为片段结束于最后一个节点。以 prev=null 开始,循环得到 ,dummy 的 next 是 。反转整个链表是 、 的特例。
要避免的错误
常见错误
(在循环之前就重新连接前驱)
若在循环之前执行 before.next = prev,此时 prev 仍等于 after。在“追踪中间片段”一题中,这会令 ,得到 ,节点 、、 从头已无法到达。前驱必须在循环建好反转链之后才重新连接。