1 / 4思路
Merge Two Sorted Lists
思路
两条链表已经有序,每次取较小的头结点接到结果尾部。用哑结点避免单独处理第一个结点;某一条走完后,把另一条剩余部分整体接上。
复杂度
- 时间 O(m + n):每个结点访问一次。
- 空间 O(1):迭代写法只改指针。
代码
- Python
- TypeScript
class ListNode:
def __init__(self, val: int = 0, next: "ListNode | None" = None):
self.val = val
self.next = next
def merge_two_lists(l1: ListNode | None, l2: ListNode | None) -> ListNode | None:
dummy = ListNode()
tail = dummy
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 or l2
return dummy.next
function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
const dummy = new ListNode();
let tail = dummy;
while (l1 && 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 ?? l2;
return dummy.next;
}
边界
- 一条为空:直接返回另一条。
- 值相等:取哪条都可以,稳定性不影响结果。
- 不能新建结点复制值:题目要求复用原结点,只改
next。