LeetCode LCR 024. 反转链表
题目描述
题意分析
将单链表的节点连接方向全部反转，并返回反转后的头节点。原来的尾节点成为新头，原头成为尾且后继应为空，节点值保持不变。
单链表只能通过
next访问后继，修改连接时必须保住尚未处理部分的入口。空链表返回空，单节点仍返回自身。原题进阶要求同时给出迭代与递归实现，下面分别说明。
解法：迭代反转链表指针
核心思路
[!blue]
将链表看成已处理与未处理两部分。
pre指向已反转部分的头，p指向尚未处理部分的头。初始时已处理部分为空，令pre = null，未处理部分从head开始。每轮把
p指向的节点移到已反转部分的最前面。先保存q = p.next，因为接下来修改p.next后，原后继就不能再通过当前节点找到。再令
p.next = pre，完成这一条边的反转；将pre更新为当前节点，p更新为保存的q。处理完一轮后，前面所有节点已倒序相连，剩余节点仍沿原方向连接，双方入口均被保存。每轮恰好处理一个节点，直到
p为空，pre就是整条反转链表的头。第一轮把原头接到空的已处理部分，也自然让它成为新尾，省去单独断尾操作。空链表不进入循环，单节点只执行一轮，两种边界都由同一流程覆盖。
解题步骤
- 初始化
pre = null、p = head。- 当前节点存在时，先保存它的旧后继
q。- 令当前节点指向
pre，再将pre移到当前节点。- 将
p移到旧后继，重复直到待处理部分为空。- 返回
pre。
代码实现
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode p = head;
while (p != null) {
// 改 p.next 之前先保住后继，否则待处理段整体丢失。
ListNode q = p.next;
p.next = pre;
pre = p;
p = q;
}
return pre;
}
}
func reverseList(head *ListNode) *ListNode {
var pre *ListNode
for p := head; p != nil; {
// 改 p.Next 之前先保住后继，否则待处理段整体丢失。
q := p.Next
p.Next = pre
pre = p
p = q
}
return pre
}
复杂度分析
- 时间复杂度：$O(n)$，每个节点访问一次、改写一次后继。
- 空间复杂度：$O(1)$，只保存当前节点、旧后继与已反转头。
关键点总结
[!green]
- 修改后继前先保存旧后继，避免丢失未处理部分。
- 每轮将一个节点头插到已反转部分，状态含义始终不变。
- 初始空前驱让原头自然变为尾节点。
- 循环结束返回已反转头，而不是已经走空的当前指针。
解法：递归反转后缀
核心思路
[!blue]
定义
reverseList(head)返回以当前head开始的整段链表反转后的新头。空链表或单节点已经反转完成，直接返回。对更长链表，先递归反转
head.next后面的全部节点。递归结束后，原第二个节点变成了这段反转后缀的尾节点，而head.next仍指向这个原第二节点，因此可以用head.next.next = head把当前头接到它后面。接好以后，当前节点成为整段的新尾，需要令
head.next = null清除旧方向的边，否则它仍指回刚才的第二节点而构成环。整段新头在递归中已经得到，回溯时保持它不变并返回。子问题规模每次减少一个节点，到尾节点后逐层接回，完整实现所有边反向。节点仍原地复用，但递归调用占用线性栈空间。
解题步骤
- 当前节点为空或没有后继时直接返回。
- 递归反转后缀，保存返回的新头。
- 将后缀的新尾接向当前头，再将当前头的旧后继清空。
- 返回递归得到的新头。
代码实现
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}
func reverseList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
newHead := reverseList(head.Next)
head.Next.Next = head
head.Next = nil
return newHead
}
复杂度分析
- 时间复杂度：$O(n)$，每个节点对应一次调用，每层只做常数次连接。
- 空间复杂度：$O(n)$，来自递归调用栈，不是常数额外空间。
关键点总结
[!green]
- 先让后缀反转完成，再将当前头接到后缀的新尾。
head.next保留了原第二节点引用，它在递归后恰好是后缀尾。- 接回当前头后必须断开旧边，才能保持无环。
- 迭代与递归都复用节点，额外空间差异来自调用栈。
易错点总结
[!yellow]
- 没保存后继就覆盖
next，会失去继续访问剩余链表的入口。- 迭代条件只检查
p.next，会漏掉最后一个节点，并且不能自然处理空输入。pre不能初始化为head，否则第一次连接会形成自环。- 反转非空链后，原
head位于新尾；统一返回pre才能得到完整结果。- 递归回溯后不清空原头的旧后继，会让最后两个节点相互指向而形成环。
- 递归返回的是整段新头，不能在回溯每一层时改为返回当前原头。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 92. 反转链表 II | 中等 | 把整条链表反转限制到给定区间，额外保存区间前驱并接回两端。 |
| 25. K 个一组翻转链表 | 困难 | 把反转作为子过程，每k个节点处理一次，并保留不足k的尾段。 |