Add Two Numbers：链表逐位相加，关键在 carry

本期讲 LeetCode Hot 100 / Top 100 Liked 里的链表题 Add Two Numbers。题目给出两个非空链表，数字按反向顺序存储：头节点就是个位。我们不把链表转成整数，而是同步遍历两个链表，逐位相加并把进位带到下一轮。

核心思路：

l1 和 l2 同步向后走，缺位按 0 处理。
sum = val1 + val2 + carry。
当前结果节点写 sum % 10。
下一轮进位写 Math.floor(sum / 10)。
用 dummy 节点挂住答案链表，最后返回 dummy.next。

function addTwoNumbers(l1, l2) {
  const dummy = new ListNode(0);
  let cur = dummy;
  let carry = 0;

while (l1 || l2 || carry) {
    const val1 = l1 ? l1.val : 0;
    const val2 = l2 ? l2.val : 0;
    const sum = val1 + val2 + carry;

cur.next = new ListNode(sum % 10);
    carry = Math.floor(sum / 10);
    cur = cur.next;

l1 = l1 ? l1.next : null;
    l2 = l2 ? l2.next : null;
  }

return dummy.next;
}

复杂度：时间复杂度 O(m + n)，其中 m 和 n 是两条链表长度；空间复杂度 O(m + n)，用于存放结果链表。

LeetCode Hot 100：Add Two Numbers 图解 JavaScript 解法

Add Two Numbers：链表逐位相加，关键在 carry

来源

Related content