LeetCode 206. 反转链表
目录
题目描述
题意分析
给定单链表头节点
head，把整条链表的方向反过来，返回反转后的新头节点。要求原地反转，不允许重建一条新链表。单链表的全部约束都来自一条：只能沿
next向后走，拿不到前驱。反转恰恰要求每个节点指向它原来的前驱，所以必须在遍历过程中自己把前驱「记住」。由此引出这道题唯一的技术难点——指针操作的顺序。一旦执行
cur.next = pre，cur原来的后继就再也找不回来了，后面整条未处理的链表全部丢失。所以每一步必须先保存后继，再改指针。这个「三指针 + 暂存」的手法是所有链表反转类题目的公共骨架。反转后的新头节点是原链表的最后一个节点，因此返回值不可能是原
head——原head反转后变成了尾节点。这一点是本题最高频的返回值错误。边界：链表为空时返回空；只有一个节点时反转后仍是它自己。好的实现应该让这两种情况自然落入主逻辑，而不需要额外的特判分支。
解法：迭代反转指针
核心思路
遍历链表时把当前节点的
next指向前一个节点。改指针前先保存原来的后继，否则会丢失剩余链表。
解题步骤
prev指向已反转部分的头节点，初始为null。- 保存
curr.next，再令curr.next = prev。prev、curr依次向前移动。curr为空时，prev就是新头节点。
代码实现
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)$。
- 空间复杂度：$O(1)$。
关键点总结
- 顺序固定：保存后继、反转指针、移动双指针。
prev始终是已反转部分的头节点。- 迭代解法没有递归栈，更适合作为默认写法。
易错点总结
- 未保存
next就修改curr.next，会断开剩余链表。- 返回
head或curr；循环结束时应返回prev。- 空链表和单节点链表无需特殊分支。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 92. 反转链表 II | 中等 | 只反转 [left, right] 区间，需借哨兵定位前驱并重新接回两端 |
| 25. K 个一组翻转链表 | 困难 | 分组反转，每组套用本题骨架，还要处理不足 k 个的尾部 |
| 24. 两两交换链表中的节点 | 中等 | k = 2 的特例，可直接三指针交换，也可套 25 题的通用解 |
| 143. 重排链表 | 中等 | 快慢指针找中点 + 反转后半段 + 交替合并，本题是其中一步 |
| 234. 回文链表 | 简单 | 反转后半段再逐一比对，可做到 $O(1)$ 空间 |
| LCR 024. 反转链表 | 简单 | 与本题同题，可直接套用 |
| 剑指 Offer 24. 反转链表 | 简单 | 与本题同题，可直接套用 |
| LCR 026. 重排链表 | 中等 | 与 143 同题 |
| LCR 027. 回文链表 | 简单 | 与 234 同题 |
| 面试题 02.06. 回文链表 | 简单 | 与 234 同题 |
| 补充题 18. 反转双向链表 | 中等 | 双向链表要同时翻转 pre 与 next，交换后头尾也要互换 |