在链表类算法中「合并两个有序链表」是一道非常经典的基础题。它看似简单只是把两个已经升序排列的链表合并成一个新的升序链表但实际上这道题集中体现了链表算法中的几个核心思想第一如何使用指针连接节点第二如何避免复杂的头节点特判第三如何理解“原地拼接”与“新建节点”的区别第四如何在迭代和递归两种思维之间切换。本文将以 LeetCode 21 题为例系统讲解这道题的解法、代码实现、执行过程和背后的算法设计思想。一、题目描述题目要求如下给定两个升序链表list1和list2将它们合并为一个新的升序链表并返回。新链表是通过拼接给定两个链表中的所有节点组成的。例如输入 list1 [1, 2, 4] list2 [1, 3, 4] 输出 [1, 1, 2, 3, 4, 4]如果其中一个链表为空那么直接返回另一个链表即可。例如输入 list1 [] list2 [0] 输出 [0]二、问题本质分析这道题的本质是合并两个已经有序的线性结构。如果把链表换成数组这个问题其实就是归并排序中的“归并”过程。例如A [1, 2, 4] B [1, 3, 4]合并过程就是每次比较两个序列当前元素选择较小的那个放入结果序列。对于数组来说我们通常使用下标i和j。对于链表来说我们使用指针list1和list2。数组合并是移动下标链表合并是移动节点指针。三、为什么不能像数组一样直接访问链表和数组最大的区别在于数组支持随机访问nums[i]而链表不支持随机访问。链表只能通过next指针逐个向后遍历node node-next;所以链表问题的关键不是“下标移动”而是“指针连接”。在这道题中我们要做的不是创建一个数组也不是排序所有节点而是利用两个链表本身已经有序的性质通过指针重新连接节点。四、核心思想双指针 虚拟头节点我们设置三个指针list1 list2 cur其中list1指向第一个链表当前待处理节点list2指向第二个链表当前待处理节点cur指向合并后链表的尾部。每次比较list1-val 和 list2-val如果list1-val更小就把list1当前节点接到结果链表后面。否则把list2当前节点接到结果链表后面。然后移动对应链表的指针。五、虚拟头节点 dummy 的作用在链表题中虚拟头节点是一个非常常用的技巧。如果不用虚拟头节点那么我们需要单独处理结果链表的第一个节点。例如我们可能需要写出这样的逻辑ListNode* head nullptr; ListNode* cur nullptr; if (list1-val list2-val) { head list1; cur list1; list1 list1-next; } else { head list2; cur list2; list2 list2-next; }这样代码会比较繁琐而且容易出错。使用虚拟头节点后代码会变得非常统一ListNode dummy(0); ListNode* cur dummy;dummy本身不是最终链表的一部分它只是一个辅助节点。所有真实节点都接在dummy.next后面。最终返回return dummy.next;这样就避免了对头节点的特殊判断。六、迭代法代码实现/** * 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) { ListNode dummy(0); ListNode* cur dummy; while (list1 ! nullptr list2 ! nullptr) { if (list1-val list2-val) { cur-next list1; list1 list1-next; } else { cur-next list2; list2 list2-next; } cur cur-next; } cur-next list1 ! nullptr ? list1 : list2; return dummy.next; } };七、代码逐行解析先创建虚拟头节点ListNode dummy(0);这个节点的值没有实际意义它只是为了统一链表拼接逻辑。然后定义尾指针ListNode* cur dummy;cur永远指向当前合并链表的最后一个节点。接下来进入循环while (list1 ! nullptr list2 ! nullptr)只要两个链表都没有遍历完就继续比较它们的当前节点。如果第一个链表当前节点更小if (list1-val list2-val) { cur-next list1; list1 list1-next; }这里做了两件事第一把list1当前节点接到结果链表后面第二让list1指针向后移动。如果第二个链表当前节点更小else { cur-next list2; list2 list2-next; }同理把list2当前节点接到结果链表后面然后移动list2。每接入一个节点后都要移动结果链表的尾指针cur cur-next;当循环结束时说明至少有一个链表已经遍历完。由于两个链表本身都是升序的所以剩下的链表可以直接整体接到结果链表后面cur-next list1 ! nullptr ? list1 : list2;最后返回真正的头节点return dummy.next;八、执行过程演示假设输入为list1 1 - 2 - 4 list2 1 - 3 - 4初始状态dummy - nullptr list1 - 1 - 2 - 4 list2 - 1 - 3 - 4 cur - dummy第一次比较list1-val 1 list2-val 1因为list1-val list2-val所以接入list1当前节点dummy - 1 list1 - 2 - 4 list2 - 1 - 3 - 4 cur - 1第二次比较list1-val 2 list2-val 1接入list2当前节点dummy - 1 - 1 list1 - 2 - 4 list2 - 3 - 4 cur - 1第三次比较list1-val 2 list2-val 3接入list1当前节点dummy - 1 - 1 - 2 list1 - 4 list2 - 3 - 4 cur - 2继续比较依次接入3、4最终得到dummy - 1 - 1 - 2 - 3 - 4 - 4返回dummy.next即1 - 1 - 2 - 3 - 4 - 4九、为什么最后可以直接接上剩余链表这是因为输入链表本身已经是升序排列的。假设循环结束时list2已经为空而list1还有剩余节点list1 4 - 5 - 8 list2 nullptr由于list1本身有序并且当前结果链表最后一个节点一定不大于list1当前节点所以可以直接接上cur-next list1;没有必要继续一个节点一个节点地比较。这一步既简洁又提高了代码可读性。十、递归解法这道题也可以用递归来写。递归思路是如果list1的当前节点更小那么list1当前节点应该作为合并后链表的头节点。它后面的部分应该由mergeTwoLists(list1-next, list2)继续合并。代码如下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; } } };十一、递归代码解析递归终止条件是if (list1 nullptr) { return list2; } if (list2 nullptr) { return list1; }如果某一个链表已经为空那么合并结果就是另一个链表。递归主体是if (list1-val list2-val) { list1-next mergeTwoLists(list1-next, list2); return list1; }这段代码的含义是当前list1节点较小因此它应该放在合并后链表的最前面。至于它后面的节点应该如何排列交给递归函数继续处理。同理else { list2-next mergeTwoLists(list1, list2-next); return list2; }表示当前list2节点更小因此返回list2作为当前阶段的头节点。十二、迭代法与递归法对比方法优点缺点迭代法空间复杂度低执行过程直观适合工程代码代码略长递归法代码简洁逻辑优雅存在递归栈开销对于这道题链表节点数最多只有50所以递归法完全可以通过。但是从工程实践角度来看更推荐迭代法。原因是迭代法不会产生额外的递归栈空间在链表长度较大时更加稳定。十三、复杂度分析假设两个链表长度分别为m和n。1. 时间复杂度无论使用迭代法还是递归法每个节点最多被访问一次。所以时间复杂度为O(m n)2. 空间复杂度迭代法只使用了常数个指针变量O(1)递归法需要函数调用栈最坏情况下递归深度为m nO(m n)十四、常见错误分析1. 忘记移动 cur 指针错误写法cur-next list1; list1 list1-next;如果没有执行cur cur-next;那么后续节点会一直覆盖cur-next导致链表连接错误。2. 忘记接上剩余链表错误写法while (list1 ! nullptr list2 ! nullptr) { ... } return dummy.next;如果循环结束后直接返回就会丢失未遍历完的剩余节点。必须补上cur-next list1 ! nullptr ? list1 : list2;3. 不使用 dummy 导致头节点逻辑复杂不使用虚拟头节点当然也可以写但需要额外判断新链表是否为空。这会增加代码分支也更容易出现空指针问题。在链表题中只要涉及“构造新链表”“删除节点”“分割链表”等操作都可以优先考虑使用虚拟头节点。十五、这道题背后的算法意义虽然 LeetCode 21 是简单题但它的重要性很高。它不仅是链表基础操作题也是很多高级问题的基础模块。例如合并 K 个升序链表归并排序链表链表排序链表分治算法外部排序中的多路归并数据库和搜索系统中的有序流合并。尤其是 LeetCode 23「合并 K 个升序链表」本质上就是 LeetCode 21 的扩展版本。如果能熟练掌握两个有序链表的合并那么之后理解多链表合并、链表归并排序会轻松很多。十六、最终推荐写法综合可读性、空间复杂度和工程稳定性最推荐的写法是迭代法class Solution { public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode dummy(0); ListNode* cur dummy; while (list1 ! nullptr list2 ! nullptr) { if (list1-val list2-val) { cur-next list1; list1 list1-next; } else { cur-next list2; list2 list2-next; } cur cur-next; } cur-next list1 ! nullptr ? list1 : list2; return dummy.next; } };这段代码具有几个优点逻辑清晰没有复杂特判不额外创建新节点空间复杂度为O(1)适合作为链表合并类问题的模板。十七、总结「合并两个有序链表」是一道典型的链表双指针题。它的核心不是排序而是利用两个链表已经有序的性质通过比较当前节点将较小节点接入结果链表。整道题的关键点有三个第一使用两个指针分别遍历两个链表第二使用虚拟头节点简化结果链表的构造第三循环结束后直接接上剩余链表。从算法思想上看这道题本质上是归并过程在链表结构上的体现。从代码技巧上看它是学习链表指针操作、虚拟头节点和递归思想的重要基础题。掌握这道题之后再学习「合并 K 个升序链表」「排序链表」「链表归并排序」等问题会更加自然。