反转链表（Reverse Linked List）
力扣第 206 题。把一条单链表原地反转，返回新头节点。
解法一：迭代（最优，O(1) 空间）⭐
用三个指针滚动推进，每次把当前节点的 next 指针掉头。
cpp
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr != nullptr) {
ListNode* next = curr->next; // 先保存后继，否则断链后找不到
curr->next = prev; // 掉头
prev = curr; // prev 前进
curr = next; // curr 前进
}
return prev; // curr 为 null 时，prev 正好是新头
}
走一遍例子：
原链表: 1 → 2 → 3 → 4 → null 初始: prev=null, curr=1 第1步: next=2, 1→null, prev=1, curr=2 第2步: next=3, 2→1, prev=2, curr=3 第3步: next=4, 3→2, prev=3, curr=4 第4步: next=null, 4→3, prev=4, curr=null 返回 prev=4，即新头 结果: 4 → 3 → 2 → 1 → null ✓
解法二：递归（理解指针递归的好题）
cpp
ListNode* reverseList(ListNode* head) {
// 递归终止：空链表或只有一个节点
if (head == nullptr || head->next == nullptr)
return head;
// 递归反转后半段，new_head 是反转后的新头
ListNode* new_head = reverseList(head->next);
// 此时 head->next 仍指向原来的下一个节点（现在是反转链表的尾节点）
// 把它的 next 指回 head，完成最后一步拼接
head->next->next = head;
head->next = nullptr; // head 成为新尾，断掉原来的前向指针
return new_head;
}
递归过程可视化（以 1→2→3 为例）：
reverseList(1)
└─ reverseList(2)
└─ reverseList(3) 返回 3（新头）
2->next->next = 2 即 3→2
2->next = null
返回 3
1->next->next = 1 即 2→1
1->next = null
返回 3
递归写法思路优雅，但调用栈深度是 O(n)，链表很长时有栈溢出风险。
两种解法对比
| 迭代 | 递归 | |
|---|---|---|
| 时间 | O(n) | O(n) |
| 空间 | O(1) | O(n) 调用栈 |
| 面试推荐 | ★★★★★ | ★★★★ 用来秀理解 |
进阶变体：反转链表 II（力扣 92 题）
只反转第 left 到 right 位置的子链表，其余不动。
cpp
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode dummy(0);
dummy.next = head;
ListNode* pre = &dummy;
// 找到第 left-1 个节点
for (int i = 1; i < left; i++) pre = pre->next;
ListNode* curr = pre->next;
// 用"头插法"把 [left, right] 段反转
for (int i = 0; i < right - left; i++) {
ListNode* next = curr->next;
curr->next = next->next;
next->next = pre->next;
pre->next = next;
}
return dummy.next;
}
头插法是这道题的精髓：不改变 curr 指针，每次把 curr 后面的节点”摘下来”插到 pre 后面，一趟循环搞定，O(1) 空间。
面试建议
迭代写法是必须烂熟于心的，三个指针的滚动顺序（先存 next、再掉头、再移动）要能闭眼写出来。递归版本可以作为”第二种思路”补充，展示对指针和递归的深层理解。