合并两个有序链表
Merge Two Sorted Lists
本机进度仅保存在当前浏览器
题目描述
将两个升序链表合并为一个新的升序链表并返回，新链表由拼接给定的两个链表的所有节点组成。
示例：1 -> 2 -> 4 与 1 -> 3 -> 4 合并得 1 -> 1 -> 2 -> 3 -> 4 -> 4。
解题思路
- 与归并排序的合并步骤同构：每次比较两链表头节点，摘下较小者接到结果尾部。
- 引入哑节点（dummy）统一"第一个节点"的接法，免去对头节点的特判，最后返回 dummy.next。
- 一条链耗尽后，另一条剩余部分天然有序且都大于已接结果，直接整体接上即可。
参考实现
查看参考实现Python · 建议先自行作答
def mergeTwoLists(l1, l2):
# 哑节点简化头部接法
dummy = tail = ListNode(0)
while l1 and l2:
if l1.val <= l2.val:
tail.next = l1
l1 = l1.next
else:
tail.next = l2
l2 = l2.next
tail = tail.next
tail.next = l1 if l1 else l2
return dummy.next