先记住这个答案
用prev初始为null,curr指向头节点,每次循环先保存next = curr.next,然后让curr.next = prev,再把prev和curr分别推进到curr和next。循环停止时,prev是新链表头。如此每个节点只遍历一次,空间仅用三个指针,时间O(n),空间O(1)。
- 必须先保存后继再改指针
- prev从null开始,循环完是头
- 只遍历一次,O(1)额外内存
三指针更新顺序为何是反转命脉
若直接让curr.next = prev而不同时保留原后继,则链表从当前节点之后的部分全部丢失。因此每次循环必须先把next = curr.next记录下来。这个临时变量本质上是为下一轮准备的游标,它确保当前节点被改写后仍能到达未处理的节点。正确顺序是:保存next → 翻转curr.next → 推进prev和curr。
循环不变量是:进入循环前,prev指向已反转子链表的头,curr指向原链表剩余部分的头。每次迭代把curr接到prev之前,使不变量保持。循环结束时curr为null,prev成为整个链表的新头。由于每次操作常数时间,总时间O(n),空间O(1)。下列代码完整演示该过程。
function ListNode(val) {
this.val = val;
this.next = null;
}
function reverseList(head) {
let prev = null;
let curr = head;
while (curr !== null) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
function toArray(head) {
const arr = [];
while (head) {
arr.push(head.val);
head = head.next;
}
return arr;
}
// build 1->2->3->4->5
const head1 = new ListNode(1);
head1.next = new ListNode(2);
head1.next.next = new ListNode(3);
head1.next.next.next = new ListNode(4);
head1.next.next.next.next = new ListNode(5);
console.log(JSON.stringify(toArray(reverseList(head1)))); // [5,4,3,2,1]
// empty list
const head2 = null;
console.log(JSON.stringify(toArray(reverseList(head2)))); // []
// single node
const head3 = new ListNode(7);
console.log(JSON.stringify(toArray(reverseList(head3)))); // [7]查看输出与解释
[5,4,3,2,1]
[]
[7]代码逐一注释了测试用例,输出验证了空链表、单节点和五节点三种情况的正确结果,时间复杂度O(n),空间复杂度O(1)。
在栈受限环境中反转长链表
某嵌入式系统需反转一条10万节点的单向消息队列,但运行环境的任务栈仅8KB,不允许递归调用。若用递归,每个调用帧约占用几十字节,深度10万必然栈溢出。迭代法只占用prev、curr、next三个指针变量,常数内存即可完成。实现时只需传入头节点,返回值作为新头,测试用例验证结果与原始顺序完全相反。
处理过程还应防御输入异常:若头节点为null则返回null,若只有一个节点则返回自身。循环中的while(curr !== null)天然涵盖这两种情况,无需另写分支。实际测试时分别用空链表、单节点和普通多节点链表检查,确保所有路径都正确。
哪些条件会导致迭代反转失效
如果链表存在环,curr永远不会变为null,循环将无限执行。反转前应先检测环,可用快慢指针,一旦发现环则中止。另外,如果链表节点被并发线程同时修改,反转过程中可能读到不一致的next,产生悬空指针。这种情况需要加锁或采用不可变节点复制方案。
还有一种隐蔽错误:交换更新顺序,先移动prev和curr再保存next,会丢失剩余节点。例如把curr = curr.next写在next = curr.next之前,后续无法继续。因此必须严格遵守保存、翻转、移动的顺序。测试时可用较长链表观察结果是否完整,并利用打印或对比数组长度来发现断链。
容易答错的地方
- 先移动指针再保存next
- 错误:把
prev = curr; curr = curr.next;写在保存next之前,导致curr.next已被改写,原后继丢失。纠正:必须先next = curr.next,再翻转curr.next,然后移动指针。 - 忽略空链表的特殊处理
- 有的写法对空链表单独判断,其实没必要。循环条件自然处理:
curr为null时直接跳过,返回prev(初始为null)。但若错误地访问curr.next就会空指针异常,所以循环体必须放在while内。
面试官还会怎么问?
迭代反转与递归反转在时间空间上有什么差异?
迭代法时间O(n)、空间O(1);递归法时间O(n),但隐式栈空间O(n),长链表容易栈溢出。递归代码更简洁,但生产环境迭代更稳妥。
如何反转链表的指定区间(第m到n个节点)?
先遍历到第m-1个节点记录上下文,再用三指针法反转子链表,最后将子链表头尾与原链表前后部分连接。注意m=1时需更新头节点。
反转后原先的头节点如何处理?
原先的head节点最终会变成尾节点,其next应为null。在迭代中,第一次循环设其next=null,后续不会再被引用,因此正确。若忘记初始prev=null,旧头会保留原有next形成环。
参考资料
示例用于理解所注明的运行环境与边界;延伸学习可结合原文中的更多案例。