反转链表
Reverse Linked List
给你一条单链表的头节点 head，把整条链的指向反转，返回新的头节点。
在力扣中练习题目描述
head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2] 输出：[2,1]
示例 3：
输入：head = [] 输出：[]
提示：
- 链表中节点的数目范围是
[0, 5000] -5000 <= Node.val <= 5000
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
解题思路
迭代 · 双指针
prev / cur 一起往右推，边走边掉头
链表只能单向走。一旦把某个节点的 next 改掉，就再也回不到它的后继了，所以反转时必须先把后继存下来。
用自拟输入 [8, -3, 8, 0, 6, 4] 推演，结果为 [4, 6, 0, 8, -3, 8]。先看清第一轮，再观察两段链表怎样变化；两个值为 8 的节点用 #0 与 #2 区分。
维护两个指针：prev 表示当前节点应该指向谁（初始为 nullptr），cur 是正在处理的节点（初始为 head）。
prev→ null每一步做三件事，顺序不能乱：先存后继，再让当前节点掉头，最后两个指针一起右移。
prev 从空链开始，cur 指向原来的头节点。
prev→ null当 cur 走到 nullptr 时，prev 正好停在原来的尾节点上，它就是新的头节点。
cur→ nullnxt→ null所以要返回 prev 而不是 head —— head 这会儿已经是新链表的尾巴了。
易错点
- 返回 head 而不是 prev —— head 反转后已经是尾节点，返回它会得到只含一个节点的链表。
- 先执行 cur->next = prev 再存 nxt，后续节点全部丢失。
- 循环条件写成 while (cur->next)，会漏掉最后一个节点。
递归
先反转后半段，再把自己接回尾巴
正确的递归写法，额外使用 O(n) 调用栈；主解法迭代只需 O(1) 额外空间。
递归的思路换个角度：先把 head 后面的链表反转好，再处理 head 自己。
假设 head->next 之后的链已经被反转成 ... ← n2 ← n1，此时：
head->next仍然指向 n1（原链的第二个节点），而 n1 现在是反转后链表的尾节点；- 想让 head 接在后面，只需要让尾巴反过来指向 head：
head->next->next = head； - 再把 head 自己的 next 断开：
head->next = nullptr。
递归到最后一个节点时它自己就是新链表的头，于是 newHead 一路透传上来。
两种写法时间复杂度都是 O(n)；递归会占用 O(n) 的调用栈，链表很长（本题上限 5000）时有爆栈风险，工程上优先用迭代。
- 1递归到链表末尾，把最后一个节点作为 newHead 返回。
- 2回溯时，让 head->next 的 next 指回 head。
- 3把 head->next 置空，断开原来的正向连接。
- 4一路把 newHead 透传到最外层。
易错点
- 忘记 head->next = nullptr，会形成环，遍历时死循环。
- 先改 head->next 再访问 head->next->next，指针已经失效。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
head = [8, -3, 8, 0, 6, 4]prev 从空链开始，cur 指向原来的头节点。
prev→ null查看 C++ 代码
延伸阅读
- 反转是链表题的「基本动作」：K 个一组翻转（25）、两两交换（24）、回文链表（234）都建立在它之上。
- 想把链表的某一段反转，可以先定位到前驱节点，再对这段单独跑一遍同样的三行代码。
- 「先保存后继，再改指向」这个顺序，在删除节点、重排链表里同样适用。