01

60 秒回答模板

如果链表按低位在前存储，如 2->4->3 表示 342，那么可以同时遍历两个链表，每轮取当前位值和 carry 相加，生成 sum % 10 的新节点，carry = Math.floor(sum / 10)，直到两个链表和 carry 都为空。若链表按高位在前存储，则可以先反转链表，或用栈从低位弹出相加。面试时要讲清输入位序、链表长度不同、最后进位、是否允许修改原链表，以及时间 O(n)、空间 O(n) 或原地改造的取舍。

考点 位序确认
难度 真实面经题
回答目标 讲清原理、实现和边界
02

深入解析

01

先确认位序

链表大数题最关键的澄清是低位在前还是高位在前。低位在前可以直接从头相加，高位在前通常要反转或借助栈，否则会从最高位开始无法处理进位。

02

逐位相加

同时移动两个链表指针，空节点按 0 处理。当前位相加再加 carry，新节点保存个位数，carry 保存十位进位，下一轮继续参与计算。

03

处理长度差

两个数字长度可能不同，短链表遍历完后仍要继续处理长链表剩余位。循环条件应是任一链表未结束或 carry 不为 0，不能只按较短链表停止。

04

最后进位

例如 999 + 1 最后会留下 carry = 1，需要额外创建一个节点。漏掉这个节点是手写题最常见的边界错误，也会让结果少一位。

05

空间和原地取舍

最稳妥的做法是创建新链表，避免修改输入。如果面试官要求节省空间，可以复用较长链表节点，但代码复杂度和副作用要说明清楚。

javascript

低位在前的链表大数相加

function addTwoNumbers(l1, l2) {
  const dummy = { val: 0, next: null };
  let tail = dummy;
  let carry = 0;

  while (l1 || l2 || carry) {
    const left = l1 ? l1.val : 0;
    const right = l2 ? l2.val : 0;
    const sum = left + right + carry;
    tail.next = { val: sum % 10, next: null };
    tail = tail.next;
    carry = Math.floor(sum / 10);
    l1 = l1 ? l1.next : null;
    l2 = l2 ? l2.next : null;
  }

  return dummy.next;
}
  • 这段代码假设链表低位在前；高位在前时可先反转链表，或用栈从低位开始弹出。
  • 循环条件必须包含 carry，否则 999 + 1 会漏掉最高位的 1。
03

易错点

  • 不要没有确认位序就直接写代码。
  • 不要在一个链表结束后停止循环，另一个链表和 carry 仍需处理。
  • 不要忘记 9+1 这类末尾进位场景。
04

面试官追问

高位在前不能修改链表怎么办？

可以把两个链表的值压入栈，再从栈顶弹出低位相加，头插法构造结果链表。

如何处理输入为空？

可以把空链表视为 0，若两者都为空按约定返回空或单节点 0，面试中要说明返回约定。

时间和空间复杂度是多少？

遍历最长链表一次，时间 O(max(m,n))；新建结果链表需要 O(max(m,n)) 空间。