《C++ 递归、搜索与回溯》第2-3题：合并两个有序链表，反转链表-洪萨配资

《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) {} * }; */classSolution{public:ListNode*mergeTwoLists(ListNode*list1,ListNode*list2){// 递归终止条件：有一个链表为空，直接返回另一个if(list1==nullptr)returnlist2;if(list2==nullptr)returnlist1;// 选择较小的一个作为头节点，递归处理剩余部分if(list1->val<list2->val){list1->next=mergeTwoLists(list1->next,list2);returnlist1;}else{list2->next=mergeTwoLists(list1,list2->next);returnlist2;}}};

一句话记忆递归版精髓：
“谁小谁当头，头后面接上剩下的两个链表的合并结果”

推荐写法2：迭代 + 哑节点（生产最稳）

classSolution{public:ListNode*mergeTwoLists(ListNode*list1,ListNode*list2){ListNodedummy(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;returndummy.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：迭代三指针（最推荐生产写法）

classSolution{public:ListNode*reverseList(ListNode*head){ListNode*prev=nullptr;ListNode*curr=head;while(curr){ListNode*nextTemp=curr->next;// 先保存下一个节点curr->next=prev;// 反指prev=curr;// 前进一步curr=nextTemp;}returnprev;// 最后prev就是新头}};

推荐写法2：递归（面试炫技版）

classSolution{public:ListNode*reverseList(ListNode*head){// 终止条件：空链表或只有一个节点，直接返回if(!head||!head->next){returnhead;}// 递归到最后一个节点（新头）ListNode*newHead=reverseList(head->next);// 反转指针：当前节点的下一个节点的下一个指向当前节点head->next->next=head;// 断开原连接（防止形成环）head->next=nullptr;returnnewHead;}};