跳到主要内容

1 / 4思路

Add Two Numbers

原题

思路​

两个链表已经是逆序,直接从低位到高位相加。用哑结点简化头结点处理,carry 保存进位;循环条件是“两个链表还有节点,或者还有进位”。

复杂度​

  • 时间 O(max(m, n)):两条链表各走一遍。
  • 空间 O(1):只分配结果链表,不计返回值。

代码​

class ListNode:
def __init__(self, val: int = 0, next: "ListNode | None" = None):
self.val = val
self.next = next


def add_two_numbers(l1: ListNode | None, l2: ListNode | None) -> ListNode | None:
dummy = ListNode()
tail = dummy
carry = 0
while l1 or l2 or carry:
total = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry
carry, digit = divmod(total, 10)
tail.next = ListNode(digit)
tail = tail.next
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
return dummy.next

边界​

  • 两条链表长度不同:短的一条按 0 补齐。
  • 最高位仍有进位:循环多跑一次,生成新结点。
  • 结果为 0:哑结点保证仍能返回单个 0 结点。