【刷题日记】LeetCode 21. 合并两个有序列表

合并两个有序链表题目描述给定两个升序排列的链表将它们合并为一个新的升序链表并返回。新链表应通过拼接两个原始链表的所有节点组成。示例 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 均按非递减顺序排列解题思路合并两个有序链表是链表操作的经典问题常见解法包括递归法代码简洁但递归深度受链表长度限制空间复杂度为 O(mn)迭代法空间复杂度更优仅需常数级额外空间本文采用迭代法核心思路如下创建哑节点虚拟头节点其 next 指针将指向合并后的链表头同时遍历两个链表比较当前节点的值将较小值的节点接入结果链表尾部移动对应链表的指针继续比较当某链表遍历完毕时将另一链表的剩余部分直接拼接至尾部使用哑节点可避免对头节点为空的特殊处理使代码更统一简洁。解题步骤初始化哨兵节点dummy ListNode()作为合并链表的虚拟头节点维护尾指针tail dummy始终指向合并链表的末尾循环比较当list1和list2均非空时若list1.val ≤ list2.val将list1接入尾部并后移指针否则将list2接入尾部并后移指针每次操作后tail指针后移一位处理剩余节点将未遍历完的链表直接接至tail.next返回结果dummy.next即为合并后的有序链表