《C++ 递归、搜索与回溯》第2-3题：合并两个有序链表 & 反转链表
（2026年清晰 + 优雅写法推荐）
这两道题都是链表操作的经典题目，同时也是考察递归思维和迭代思维转换的绝佳练习题。下面给出最常用、最清晰的几种写法，并标注优缺点与推荐场景。
题目1：合并两个有序链表（Merge Two Sorted Lists）
题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：l1 = 1→2→4, l2 = 1→3→4
输出：1→1→2→3→4→4解法对比（推荐程度排序）
| 序号 | 写法 | 空间复杂度 | 可读性 | 推荐指数 | 备注与适用场景 |
|---|---|---|---|---|---|
| 1 | 递归（最优雅） | O(n+m) | ★★★★★ | ★★★★★ | 面试首选，代码最短最美 |
| 2 | 迭代（哑节点） | O(1) | ★★★★☆ | ★★★★☆ | 最稳，生产环境最常用（空间最优） |
| 3 | 迭代（不使用哑节点） | O(1) | ★★★☆☆ | ★★☆☆☆ | 边界处理麻烦，不推荐 |
推荐写法1：递归（最推荐面试写法）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
// 递归终止条件：有一个链表为空，直接返回另一个
if (list1 == nullptr) return list2;
if (list2 == nullptr) return list1;
// 选择较小的一个作为头节点，递归处理剩余部分
if (list1->val < list2->val) {
list1->next = mergeTwoLists(list1->next, list2);
return list1;
} else {
list2->next = mergeTwoLists(list1, list2->next);
return list2;
}
}
};一句话记忆递归版精髓：
“谁小谁当头，头后面接上剩下的两个链表的合并结果”
推荐写法2：迭代 + 哑节点（生产最稳）
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode dummy(0); // 哑节点（虚拟头节点）
ListNode* tail = &dummy; // 尾指针，用于拼接
while (list1 && list2) {
if (list1->val < list2->val) {
tail->next = list1;
list1 = list1->next;
} else {
tail->next = list2;
list2 = list2->next;
}
tail = tail->next; // 尾指针后移
}
// 剩余部分直接接上（最多剩一条链表）
tail->next = list1 ? list1 : list2;
return dummy.next;
}
};题目2：反转链表（Reverse Linked List）
题目描述
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例：
输入：head = 1→2→3→4→5
输出：5→4→3→2→1解法对比
| 序号 | 写法 | 空间复杂度 | 可读性 | 推荐指数 | 备注与适用场景 |
|---|---|---|---|---|---|
| 1 | 递归（优雅版） | O(n) | ★★★★★ | ★★★★☆ | 面试加分项，理解递归本质好 |
| 2 | 迭代（三指针） | O(1) | ★★★★☆ | ★★★★★ | 最稳、最常用、生产首选 |
| 3 | 头插法 | O(1) | ★★★☆☆ | ★★★☆☆ | 写法简单，但边界容易错 |
推荐写法1：迭代三指针（最推荐生产写法）
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr) {
ListNode* nextTemp = curr->next; // 先保存下一个节点
curr->next = prev; // 反指
prev = curr; // 前进一步
curr = nextTemp;
}
return prev; // 最后prev就是新头
}
};推荐写法2：递归（面试炫技版）
class Solution {
public:
ListNode* reverseList(ListNode* head) {
// 终止条件：空链表或只有一个节点，直接返回
if (!head || !head->next) {
return head;
}
// 递归到最后一个节点（新头）
ListNode* newHead = reverseList(head->next);
// 反转指针：当前节点的下一个节点的下一个指向当前节点
head->next->next = head;
// 断开原连接（防止形成环）
head->next = nullptr;
return newHead;
}
};递归版一句话理解：
“先递归到链表尾部，然后从后向前依次把每个节点的next指针反指回来”
总结对比表（快速背诵）
| 题目 | 推荐写法优先级 | 空间 | 时间 | 面试得分 | 生产稳健度 |
|---|---|---|---|---|---|
| 合并有序链表 | 递归 > 迭代哑节点 | O(n) | O(n+m) | 递归最高 | 迭代最高 |
| 反转单链表 | 迭代三指针 > 递归 | O(1) | O(n) | 递归炫技 | 迭代最高 |
建议练习顺序：
- 先手写迭代版合并和迭代版反转（最稳）
- 再写递归版两种（加深递归理解）
- 最后尝试不看代码默写两道题的递归+迭代各一遍
这两道题练熟了，链表递归的“从后向前处理”思维就会非常扎实，为后续的很多题目（如回文链表、链表排序、LRU缓存等）打下坚实基础。
你现在想继续练哪一道？
或者想看这两道题的进阶变形（如K个一组翻转、排序链表等）？
