递归之美：合并两个有序链表的优雅解法

在算法刷题的旅程中“合并两个有序链表”LeetCode 21题是一道经典的中等难度题目。它不仅考察了对链表结构的理解还巧妙运用了递归思想用极简的代码实现了复杂的功能。今天我们就从问题分析、代码逻辑、递归过程、复杂度分析等方面深入剖析这道题目的解法。一、题目理解题目要求将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。举个例子输入l1 [1,2,4],l2 [1,3,4]输出[1,1,2,3,4,4]链表的结构是单向的每个节点包含一个值val和一个指向下一节点的指针next。我们需要通过指针操作将两个有序链表的节点“按序拼接”。二、递归解法的核心思路递归的本质是“将大问题分解为小问题直到小问题可以直接解决”。对于合并两个有序链表我们可以这样思考基准情况递归终止条件如果其中一个链表为空直接返回另一个链表因为空链表和任何链表合并结果都是另一个链表。递归逻辑比较两个链表头节点的值选择较小的那个作为“当前合并链表的头节点”然后递归地合并“当前头节点的下一个节点”和“另一个链表的头节点”并将结果赋值给当前头节点的next。三、代码逐行解析C实现先给出完整的代码再逐行讲解/** * 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* l1, ListNode* l2) { // 基准情况1l1为空返回l2剩余l2已有序 if (l1 nullptr) return l2; // 基准情况2l2为空返回l1剩余l1已有序 if (l2 nullptr) return l1; // 比较两个链表的头节点值选择较小的作为当前合并链表的头 if (l1-val l2-val) { // l1的头节点更小所以l1的next需要合并“l1的下一个节点”和“l2” l1-next mergeTwoLists(l1-next, l2); // 返回l1作为当前合并链表的头 return l1; } else { // l2的头节点更小所以l2的next需要合并“l1”和“l2的下一个节点” l2-next mergeTwoLists(l1, l2-next); // 返回l2作为当前合并链表的头 return l2; } } };1. 链表节点结构定义第2-9行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) {} };这是C中链表的节点定义包含val节点存储的整数值。next指向下一个节点的指针。三个构造函数支持无参初始化、单值初始化、值和指针同时初始化方便创建链表节点。2. 主函数mergeTwoLists第11-27行函数接收两个链表的头指针l1和l2返回合并后的链表头指针。递归终止条件第13-14行if (l1 nullptr) return l2; if (l2 nullptr) return l1;如果l1为空说明l1已经没有节点了直接返回l2此时l2的剩余部分已经是升序的。如果l2为空同理返回l1。这是递归的“出口”确保递归不会无限进行。递归逻辑第16-25行if (l1-val l2-val) { l1-next mergeTwoLists(l1-next, l2); return l1; } else { l2-next mergeTwoLists(l1, l2-next); return l2; }比较头节点值判断l1和l2的头节点哪个更小。选择较小的头节点如果l1-val l2-val则l1作为当前合并链表的头节点。此时l1的next需要指向“l1的下一个节点”和l2合并后的结果递归调用mergeTwoLists(l1-next, l2)。如果l2-val l1-val则l2作为当前合并链表的头节点。此时l2的next需要指向“l1”和“l2的下一个节点”合并后的结果递归调用mergeTwoLists(l1, l2-next)。返回当前头节点无论选择l1还是l2都将其作为当前合并链表的头返回供上一层递归使用。四、递归过程可视化以示例1为例示例1输入l1 [1,2,4],l2 [1,3,4]我们用栈帧的方式模拟递归过程初始调用mergeTwoLists(l11→2→4, l21→3→4)比较1和1l1-val l2-val成立。执行l1-next mergeTwoLists(l1-next2→4, l21→3→4)进入下一层递归。第二层调用mergeTwoLists(l12→4, l21→3→4)比较2和1l1-val l2-val。执行l2-next mergeTwoLists(l12→4, l2-next3→4)进入下一层递归。第三层调用mergeTwoLists(l12→4, l23→4)比较2和3l1-val l2-val成立。执行l1-next mergeTwoLists(l1-next4, l23→4)进入下一层递归。第四层调用mergeTwoLists(l14, l23→4)比较4和3l1-val l2-val。执行l2-next mergeTwoLists(l14, l2-next4)进入下一层递归。第五层调用mergeTwoLists(l14, l24)比较4和4l1-val l2-val成立。执行l1-next mergeTwoLists(l1-nextnullptr, l24)进入下一层递归。第六层调用mergeTwoLists(l1nullptr, l24)触发基准条件返回l24。回到第五层l1-next 4第六层的返回值返回l14。回到第四层l2-next 4第五层的返回值返回l23→4。回到第三层l1-next 3→4第四层的返回值返回l12→3→4。回到第二层l2-next 2→3→4第三层的返回值返回l21→2→3→4。回到第一层l1-next 1→2→3→4第二层的返回值返回l11→1→2→3→4→4。最终合并后的链表为1→1→2→3→4→4与示例输出一致。五、复杂度分析时间复杂度O(nm)其中 n和 m分别是两个链表的长度。每个节点都会被递归访问一次因此总的时间复杂度是两个链表长度之和。空间复杂度O(nm)递归栈的空间递归的深度最多为 nm当两个链表长度分别为 n和 m时最坏情况下需要递归 nm层。因此递归栈的空间复杂度为 O(nm)。如果使用迭代法空间复杂度可以优化到 O(1)因为只需要几个指针变量。但递归法的代码更简洁逻辑更清晰。六、总结合并两个有序链表的递归解法核心在于“分解问题”每次选择较小的头节点然后递归处理剩余部分。这种思路不仅代码简洁还能很好地体现递归“自顶向下、逐步细化”的思想。在实际刷题或面试中递归法适合快速写出逻辑清晰的代码如果需要优化空间也可以尝试迭代法用指针逐个拼接节点。但无论哪种方法理解“如何比较两个节点并选择下一个节点”的逻辑是关键。希望这篇博客能帮你彻底掌握这道经典题目的递归解法如果有疑问欢迎在评论区交流~