LeetCode 206. 反转链表
题目描述
题意分析
反转的是节点之间的连接方向：每个节点改为指向它原来的前一个节点，原尾节点成为新头节点，原头节点成为新尾节点。节点的值不变，也不需要重新创建节点。
单链表只有指向后继的
next，没有指向前驱的指针。因此，既要记住当前节点应该接到哪里，又要在修改next前保存原来的后继，否则会失去剩余链表的入口。反转完成后，新尾节点的next必须为空。空链表返回空，只有一个节点时返回该节点。题目进阶要求分别用迭代和递归实现：迭代逐个修改指针，递归先处理后面的链表，再把当前节点接到末尾。
解法：迭代反转指针
核心思路
[!blue]
从头到尾遍历，把链表分成“已经反转”和“还未处理”两部分。
prev指向已反转部分的头节点，curr指向未处理部分的第一个节点。开始时没有节点被处理，所以prev = null，curr = head。每轮把
curr从未处理部分移到已反转部分的最前面。先用next保存curr.next，再令curr.next = prev，当前节点就接到了已反转链表前面；随后令prev = curr、curr = next，两个指针重新指向各自部分的头节点。这样每轮都会反转一个节点的连接，并且通过保存的
next保留后续入口。第一轮把原头节点指向空，使它成为新尾节点；当curr为空时，所有节点都进入了已反转部分，prev就是整条链表的新头节点。
解题步骤
- 初始化
prev = null、curr = head。- 只要
curr不为空，先保存next = curr.next。- 执行
curr.next = prev，把当前节点接到已反转部分前面。- 依次更新
prev = curr、curr = next，继续处理原来的后继。- 循环结束后返回
prev。Go 代码直接用head作为当前指针，与curr含义相同。
代码实现
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}
func reverseList(head *ListNode) *ListNode {
var prev *ListNode
for head != nil {
next := head.Next
head.Next = prev
prev = head
head = next
}
return prev
}
复杂度分析
- 时间复杂度：$O(n)$，
n为链表节点数，每个节点只处理一次。- 空间复杂度：$O(1)$，只使用固定数量的节点指针。
关键点总结
[!green]
prev不只是前一个节点：它还是整段已反转链表的入口，curr.next = prev会把当前节点接到这一整段前面。- 先保存再修改：
next保留未处理部分，prev保留已反转部分，修改连接后两部分都不会丢失。- 空链表自然结束：初始
curr为空时不进入循环，返回的prev也是空。
解法：递归反转指针
核心思路
[!blue]
先明确递归函数的含义：
reverseList(head)负责反转以head开头的整条链表，并返回反转后的头节点。如果链表为空或只剩一个节点，已经不需要反转，直接返回head。对于更长的链表，先调用
reverseList(head.next)，把当前节点后面的链表反转好，得到它的新头节点newHead。递归返回后，原来的第二个节点已经成为这段链表的尾节点，而当前的head.next仍然指向它。因此执行
head.next.next = head，就能把当前节点接到这段已反转链表的末尾。随后必须令head.next = null，断开当前节点指向原第二个节点的旧连接，否则这两个节点会形成环。每层递归只把自己的
head接到已反转后缀的末尾，不会改变newHead。所以一直向上返回newHead，最终得到的就是原链表的尾节点，也就是反转后的头节点。
解题步骤
- 如果
head为空或head.next为空，直接返回head。- 递归反转
head.next开头的链表，并保存返回值newHead。- 执行
head.next.next = head，把当前节点接到已反转后缀的末尾。- 执行
head.next = null，让当前节点成为合法的新尾节点。- 返回
newHead，供上一层继续连接。
代码实现
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接到它的尾部。- 返回值始终是新头节点：
head在当前层成为尾节点，不能用它替代newHead返回。- 递归并非常数空间：虽然没有新建链表节点，仍然需要保存各层调用；链表较长时，迭代写法更稳妥。
易错点总结
[!yellow]
- 迭代时丢失后续链表：必须先保存
curr.next再反转，反转后沿curr.next前进会回到已处理部分。- 迭代时返回错误指针：循环结束后当前指针为空，新头节点应从
prev取得。- 递归时形成环：接上
head.next.next = head后，必须断开head.next；两步也不能颠倒，否则会失去后缀尾节点的入口。- 递归边界判断顺序错误：先判断
head是否为空，再访问它的next，空链表才能正常返回。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 92. 反转链表 II | 中等 | 把整条链表反转限制到给定区间，额外保存区间前驱并接回两端。 |
| 25. K 个一组翻转链表 | 困难 | 把反转作为子过程，每k个节点处理一次，并保留不足k的尾段。 |
| 143. 重排链表 | 中等 | 拆分链表后反转并重新连接；本题完整反转链表，该题从中点拆分并交替合并首尾。 |
| 234. 回文链表 | 简单 | 拆分链表后反转并重新连接；本题完整反转链表，该题反转后半段后比较对称值。 |