LeetCode 21. 合并两个有序链表（C语言详解 | 链表经典题）

一、题目描述给定两个按非递减顺序排列的链表list1和list2将它们合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例 1输入l1 [1,2,4], l2 [1,3,4] 输出[1,1,2,3,4,4]示例 2输入l1 [], l2 [] 输出[]示例 3输入l1 [], l2 [0] 输出[0]提示两个链表的节点数目范围是[0, 50]-100 Node.val 100l1和l2均按非递减顺序排列二、解题思路由于两个链表已经是有序链表我们可以使用双指针思想来解决。思路如下创建一个虚拟头节点 dummy用于简化链表操作。定义一个指针cur指向当前新链表的末尾。同时遍历list1和list2比较两个节点的值将较小的节点接到新链表后面移动对应链表指针当其中一个链表遍历结束时直接把剩余链表接到新链表末尾。示意过程list1: 1 - 2 - 4 list2: 1 - 3 - 4 比较过程 1 vs 1 - 取 list1 2 vs 1 - 取 list2 2 vs 3 - 取 list1 4 vs 3 - 取 list2 4 vs 4 - 取 list1 剩余 - 接上 list2最终结果1 - 1 - 2 - 3 - 4 - 4三、C语言代码实现/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { // 创建虚拟头节点 struct ListNode dummy; struct ListNode *cur dummy; dummy.next NULL; // 同时遍历两个链表 while(list1 ! NULL list2 ! NULL) { if(list1-val list2-val) { cur-next list1; list1 list1-next; } else { cur-next list2; list2 list2-next; } cur cur-next; } // 连接剩余链表 if(list1 ! NULL) cur-next list1; else cur-next list2; return dummy.next; }四、复杂度分析时间复杂度O(n m)n为list1的长度m为list2的长度每个节点最多访问一次。空间复杂度O(1)只使用了几个指针变量没有额外空间开销。五、为什么使用虚拟头节点如果不使用dummy新链表的第一个节点需要单独处理。例如head list1 or list2 ?代码逻辑会变复杂。使用虚拟头节点后dummy - 1 - 1 - 2 - 3 - 4 - 4最终返回dummy.next这样可以统一处理所有节点代码更加简洁清晰。六、递归解法扩展除了迭代方法还可以使用递归来实现。思路如果list1较小则list1-next与list2继续合并如果list2较小则list2-next与list1继续合并代码如下struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { if(list1 NULL) return list2; if(list2 NULL) return list1; if(list1-val list2-val) { list1-next mergeTwoLists(list1-next, list2); return list1; } else { list2-next mergeTwoLists(list1, list2-next); return list2; } }七、总结本题是链表中的经典基础题目核心思想是⭐双指针 有序链表合并关键点使用虚拟头节点简化操作每次选择较小节点接入新链表最后连接剩余链表时间复杂度O(n m)空间复杂度O(1)这道题也是很多链表题目的基础例如23. 合并 K 个升序链表148. 排序链表归并排序链表掌握这道题对于理解链表合并思想非常重要。