链表加法：进位与方向

整理来源：第二篇 - 大厂面试手写题及算法.pdf 的链表求和题。PDF 中的示例代码只展示了核心进位逻辑；本文补充输入契约、正序存储和边界测试，并过滤课程宣传内容。

1. 逆序存储：从个位开始相加

每个节点保存一个数位，链表头是个位。两个指针同步向后走，缺少的节点按 0 处理；循环条件必须包含最后一次进位。

class ListNode {
  constructor(value, next = null) {
    this.value = value
    this.next = next
  }
}

function addReverseLists(first, second) {
  const dummy = new ListNode(0)
  let tail = dummy
  let carry = 0
  let left = first
  let right = second

  while (left !== null || right !== null || carry !== 0) {
    const sum = (left?.value ?? 0) + (right?.value ?? 0) + carry
    carry = Math.floor(sum / 10)
    tail.next = new ListNode(sum % 10)
    tail = tail.next
    left = left?.next ?? null
    right = right?.next ?? null
  }

  return dummy.next
}

例如 7 -> 1 -> 6 与 5 -> 9 -> 2 表示 617 + 295，结果为 2 -> 1 -> 9。函数新建结果节点，不改变传入链表；若题目允许复用节点，可以另行讨论空间和节点身份契约。

设两条链表长度为 m、n，时间复杂度为 O(max(m, n))，结果链表之外的额外空间为 O(1)。

2. 正序存储：用栈对齐低位

当头节点是最高位时，不能直接从头节点相加。把节点值压入两个栈，再从栈顶取出个位；每次生成的新节点插到结果头部，就能保持正序且不反转输入。

function addForwardLists(first, second) {
  const left = []
  const right = []

  for (let node = first; node !== null; node = node.next) left.push(node.value)
  for (let node = second; node !== null; node = node.next) right.push(node.value)

  let head = null
  let carry = 0

  while (left.length > 0 || right.length > 0 || carry !== 0) {
    const sum = (left.pop() ?? 0) + (right.pop() ?? 0) + carry
    carry = Math.floor(sum / 10)
    head = new ListNode(sum % 10, head)
  }

  return head
}

额外空间为 O(m + n)，时间仍为 O(m + n)。如果允许暂时反转链表，可以把额外空间降到 O(1)，但必须在返回前恢复输入，除非契约明确允许修改。

3. 输入校验与边界

算法题通常保证每个节点是 0 到 9 的数位；工程代码还应决定以下行为：

空链表是否代表 0，还是非法输入；
是否允许前导零，以及结果是否需要规范化；
链表是否可能成环；
节点字段名是 value 还是 val，不要在实现中静默混用；
结果是否必须保留原节点身份，是否允许原地修改。

建议至少测试：空加空、长度不同、9 + 1、连续进位（999 + 1）、一方为零、前导零和单节点输入。数位运算不要先转成 Number，否则长链表会失去精度；若输入本来是字符串大数，可阅读大数相加。

4. 面试表达顺序

先确认数字的存储方向和节点字段。
说明 carry 的范围和循环终止条件。
用哨兵节点统一结果头部的插入边界。
说清是否修改输入，以及时间、结果空间和额外空间。
用连续进位和长度不等的样例走一遍指针。

相关专题：链表基础、双指针基础知识速览。