《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：递归（最推荐面试写法）

/** * 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：迭代三指针（最推荐生产写法）

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;}};

递归版一句话理解：
“先递归到链表尾部，然后从后向前依次把每个节点的next指针反指回来”

总结对比表（快速背诵）

建议练习顺序：

1. 先手写迭代版合并和迭代版反转（最稳）
2. 再写递归版两种（加深递归理解）
3. 最后尝试不看代码默写两道题的递归+迭代各一遍

这两道题练熟了，链表递归的“从后向前处理”思维就会非常扎实，为后续的很多题目（如回文链表、链表排序、LRU缓存等）打下坚实基础。

你现在想继续练哪一道？
或者想看这两道题的进阶变形（如K个一组翻转、排序链表等）？