1 / 4思路
Add Two Numbers
思路
两个链表已经是逆序,直接从低位到高位相加。用哑结点简化头结点处理,carry 保存进位;循环条件是“两个链表还有节点,或者还有进位”。
复杂度
- 时间 O(max(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 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
class ListNode {
val: number;
next: ListNode | null;
constructor(val = 0, next: ListNode | null = null) {
this.val = val;
this.next = next;
}
}
function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
const dummy = new ListNode();
let tail = dummy;
let carry = 0;
while (l1 || l2 || carry > 0) {
const total = (l1?.val ?? 0) + (l2?.val ?? 0) + carry;
carry = Math.floor(total / 10);
tail.next = new ListNode(total % 10);
tail = tail.next;
l1 = l1?.next ?? null;
l2 = l2?.next ?? null;
}
return dummy.next;
}
边界
- 两条链表长度不同:短的一条按 0 补齐。
- 最高位仍有进位:循环多跑一次,生成新结点。
- 结果为 0:哑结点保证仍能返回单个 0 结点。