跳到主要内容

1 / 4思路

Merge Two Sorted Lists

原题

思路​

两条链表已经有序,每次取较小的头结点接到结果尾部。用哑结点避免单独处理第一个结点;某一条走完后,把另一条剩余部分整体接上。

复杂度​

  • 时间 O(m + n):每个结点访问一次。
  • 空间 O(1):迭代写法只改指针。

代码​

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

边界​

  • 一条为空:直接返回另一条。
  • 值相等:取哪条都可以,稳定性不影响结果。
  • 不能新建结点复制值:题目要求复用原结点,只改 next。