LeetCode 206. 反转链表
题目核心
给定单链表的头节点 head，将链表的指针方向全部反转，并返回反转后的新头节点。
例如：
输入：1 -> 2 -> 3 -> null
输出：3 -> 2 -> 1 -> null反转时不能只交换节点值，真正需要改变的是每个节点的 next 指针。
解题思考过程
第一步：理解问题
反转链表的核心是改变每个节点的 next 指针方向。
原始：1 -> 2 -> 3 -> null
反转：null <- 1 <- 2 <- 3每个节点的 next 指针需要指向前一个节点。
第二步：暴力解法（栈）
最直接的思路：把所有节点压入栈，然后依次弹出，重新连接。
压栈：1, 2, 3
弹出：3 -> 2 -> 1时间复杂度：O(n)
空间复杂度：O(n) - 需要额外的栈空间这个思路可行，但需要额外空间。
第三步：思考如何原地反转
能不能在遍历链表的过程中直接反转？
想到用三个指针：
pre：前一个节点curr：当前节点next：下一个节点
遍历过程：
1. 保存 next = curr.next（因为反转后 curr.next 会变）
2. 反转 curr.next = pre
3. 移动 pre = curr
4. 移动 curr = next第四步：验证迭代反转
以 1 -> 2 -> 3 -> null 为例：
初始化：pre = null, curr = 1
第一次循环：
next = 1.next = 2
1.next = pre = null // 1 -> null
pre = 1
curr = 2
第二次循环：
next = 2.next = 3
2.next = pre = 1 // 2 -> 1 -> null
pre = 2
curr = 3
第三次循环：
next = 3.next = null
3.next = pre = 2 // 3 -> 2 -> 1 -> null
pre = 3
curr = null
循环结束，pre = 3 就是新的头节点 ✓第五步：递归解法
递归的思路是：先反转后面的链表，再处理当前节点。
递归公式：
reverseList(head) = 把 head.next 的反转结果的尾部指向 head
base case：如果 head 为空或只有一个节点，直接返回 head验证：
reverseList(1):
reverseList(2):
reverseList(3):
reverseList(null) -> 返回 null
3.next = null
返回 3
2.next = 3
3.next = 2
返回 3（新头）
1.next = 2
2.next = 1
返回 3（新头）第六步：两种方法对比
| 方法 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|
| 迭代 | O(n) | O(1) | 空间最优，推荐 |
| 递归 | O(n) | O(n) | 代码简洁，但有栈溢出风险 |
迭代方法更好，因为空间复杂度是 O(1)，而且没有栈溢出的风险。
当前解法：迭代反转
当前代码使用三个变量完成原地反转：
var reverseList = function (head) {
let pre = null;
let next = null;
while (head != null) {
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
};变量含义
三个变量分别表示：
head：当前正在处理的节点。pre：已经反转完成的链表头节点。next：提前保存的下一个节点，防止原链表后半段丢失。
代码逐行解释
var reverseList = function (head) {定义函数，参数 head 是原链表的头节点。
let pre = null;pre 初始化为 null，表示反转后的链表初始为空。当链表只有一个节点时，反转后它的 next 就是 null。
let next = null;next 用于临时保存下一个节点，需要在修改 head.next 之前把原来的值存下来。
while (head != null) {循环条件：只要当前节点不为空，就继续处理。当 head 变成 null 时，说明所有节点都已处理完毕。
next = head.next;第一步：保存下一个节点。因为接下来要修改 head.next，如果不提前保存，就会丢失对后续链表的引用。
head.next = pre;第二步：反转当前节点的指针。让当前节点指向已经反转好的部分。这是最关键的一步，改变了指针方向。
pre = head;第三步：移动 pre。把 pre 更新为当前节点，因为当前节点已经完成了反转。
head = next;第四步：移动 head。让 head 指向下一个待处理的节点，继续循环。
}
return pre;
};循环结束时，head 为 null，而 pre 指向最后一个处理的节点，也就是反转后的新头节点。
为什么必须先保存 next
执行下面这句以后：
head.next = pre;当前节点会改为指向前一个节点。如果没有提前保存原来的 head.next，就无法继续访问尚未处理的链表。
因此循环中的操作顺序不能随意交换：
保存后继节点 -> 反转当前指针 -> 移动 pre -> 移动 head反转过程
假设当前链表为：
1 -> 2 -> 3 -> null初始状态：
pre = null
head = 1
next = null第一次循环：
next = head.next → next = 2
head.next = pre → 1.next = null
pre = head → pre = 1
head = next → head = 2
已反转：1 -> null
待处理：2 -> 3 -> null第二次循环：
next = head.next → next = 3
head.next = pre → 2.next = 1
pre = head → pre = 2
head = next → head = 3
已反转：2 -> 1 -> null
待处理：3 -> null第三次循环：
next = head.next → next = null
head.next = pre → 3.next = 2
pre = head → pre = 3
head = next → head = null
已反转：3 -> 2 -> 1 -> null
待处理：null此时 head 为 null，循环结束。pre 指向新的头节点 3，所以返回 pre。
复杂度
- 时间复杂度：
O(n)，每个节点只处理一次。 - 空间复杂度：
O(1)，只使用固定数量的指针变量。
递归写法
也可以先递归反转后半部分，再把当前节点接到末尾：
var reverseList = function (head) {
if (head == null || head.next == null) {
return head;
}
const newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
};递归写法逐行解释
var reverseList = function (head) {定义递归函数。
if (head == null || head.next == null) {
return head;
}递归终止条件：如果链表为空或只有一个节点，不需要反转，直接返回。
const newHead = reverseList(head.next);递归调用：先反转当前节点之后的所有节点，返回的 newHead 是反转后的新头节点。
head.next.next = head;把当前节点接到反转后的链表末尾。原来的 head.next 现在变成了反转后链表的最后一个节点，让它的 next 指向当前节点。
head.next = null;断开当前节点与原链表的连接，防止形成环。
return newHead;
};返回新的头节点。
递归过程示例
以 1 -> 2 -> 3 -> null 为例：
reverseList(1)
→ reverseList(2)
→ reverseList(3)
→ head.next == null，返回 3
→ newHead = 3
→ 2.next.next = 2 → 3.next = 2
→ 2.next = null → 2 -> null
→ 返回 3
→ newHead = 3
→ 1.next.next = 1 → 2.next = 1
→ 1.next = null → 1 -> null
→ 返回 3
最终结果：3 -> 2 -> 1 -> null两种写法对比
| 写法 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|
| 迭代 | O(n) | O(1) | 空间更优，链表很长时更安全 |
| 递归 | O(n) | O(n) | 代码更简洁，理解起来更直观 |
递归写法的时间复杂度仍为 O(n)，但递归调用栈需要 O(n) 空间。链表很长时，迭代写法更安全，不会发生栈溢出。