LeetCode 剑指 Offer 24. 反转链表
题目描述
题意分析
给定单链表的头节点，将所有节点的后继方向反转，并返回新的头节点。原来的尾节点会成为新头，原来的头节点会成为新尾，节点本身及其值保持不变。
这是对链表连接的修改，不是只把节点值倒序输出。空链表仍返回空，单节点链表的结果仍是它自己；对于普通链表，需要在改变连接时保住尚未处理的剩余部分。
解法：迭代三指针反转
核心思路
[!blue]
把处理过程分为两段：
pre指向已经反转好的前缀，cur指向尚未处理后缀的第一个节点。开始时已反转部分为空，所以pre = null，未处理部分就是整条原链，所以cur = head。每轮从未处理部分取出当前节点，接到已反转部分的头部。首先用
next保存原来的cur.next，它是剩余后缀的入口；然后执行cur.next = pre，把当前节点的方向改为指向前面已经反转的链。接着令
pre = cur，让已反转部分包含刚处理的节点，再令cur = next，继续处理原来的后继。每轮都恰好把一个节点从未处理部分转移到已反转部分，两段仍包含原链的全部节点，不会丢失或重复处理。第一次反转时，原头的后继会被设为空，因此它最终成为正确的尾节点，不会残留向后的旧连接。之后每个当前节点都只指向已经处理的节点，也不会形成环。
当
cur为空时，未处理部分已经耗尽，pre就是整条反转链的头。原head此时指向尾节点，不能作为返回结果；空链表和单节点也会按同一流程得到正确返回值。
解题步骤
- 初始化
pre = null、cur = head。- 当
cur非空时，先将原后继保存在next中。- 执行
cur.next = pre，反转当前节点的后继方向。- 依次更新
pre = cur、cur = next，扩大已反转部分并继续后缀。- 循环结束后返回
pre。
代码实现
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
// 当前节点指回已经反转好的前半部分。
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
func reverseList(head *ListNode) *ListNode {
var pre *ListNode
cur := head
for cur != nil {
next := cur.Next
// 保存 next 后再改变指针方向。
cur.Next = pre
pre = cur
cur = next
}
return pre
}
复杂度分析
- 时间复杂度：$O(n)$，每个节点恰好处理一次，只进行常量次指针读取和修改。
- 空间复杂度：$O(1)$，只使用
pre、cur、next三个工作指针，不创建新节点或递归栈。
关键点总结
[!green]
pre与cur分别代表已反转前缀和未处理后缀，每轮只转移一个节点。- 保存原后继必须先于修改当前后继，才能继续访问未处理部分。
pre初始为空负责断开原头的旧后继，结束时pre又负责提供新头。
易错点总结
[!yellow]
- 先改写
cur.next再保存它，得到的已经是反向连接，会丢掉原来的后缀入口。- 改写连接后直接令
cur = cur.next，会沿反转后的边走回前缀，应使用之前保存的next。- 循环判断
cur.next != null，既会漏掉最后一个节点，也无法安全处理空链表，应判断cur本身。- 将
pre初始化为head，第一次操作会让原头指向自身形成环。- 返回原
head或退出时的cur都不对，前者是新尾，后者为空，正确返回值是pre。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 92. 反转链表 II | 中等 | 把整条链表反转限制到给定区间，额外保存区间前驱并接回两端。 |
| 25. K 个一组翻转链表 | 困难 | 把反转作为子过程，每k个节点处理一次，并保留不足k的尾段。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！