链表数值运算

如何把两个链表表示的整数相加（低位在头）？

• 输入形态: 每个结点存一位, 表头是最低位, 与手算顺序一致;
• 循环: l1 || l2 || carry 三选一为真就继续, 空链按 0 计入;
• 进位: sum >= 10 时 carry = 1 并把 sum %= 10;
• 结果: 用哨兵串接新结点;
• 时间 $O(\max(m, n))$, 空间 $O(1)$ 额外空间;

const addTwoNumbers = (l1, l2) => {
  const dummy = new ListNode(0);
  let cur = dummy;
  let carry = 0;
  while (l1 || l2 || carry) {
    const sum = (l1?.val ?? 0) + (l2?.val ?? 0) + carry;
    carry = sum >= 10 ? 1 : 0;
    cur.next = new ListNode(sum % 10);
    cur = cur.next;
    l1 = l1?.next ?? null;
    l2 = l2?.next ?? null;
  }
  return dummy.next;
};

低位在尾时如何相加？

• 差别: 进位方向与遍历方向相反, 需要先拿到低位;
• 办法: 把两条链的值依次压入数组, 用 pop 从低位取出相加;
• 结果构造: 每次新建结点并让 node.next = res, 相当于头插, 天然得到正序结果;
• 时间 $O(\max(m, n))$, 空间 $O(m + n)$;

const addTwoNumbersReversed = (l1, l2) => {
  const numList1 = [];
  const numList2 = [];
  for (let p = l1; p; p = p.next) numList1.push(p.val);
  for (let p = l2; p; p = p.next) numList2.push(p.val);

  let res = null;
  let carry = 0;
  while (numList1.length || numList2.length || carry) {
    const sum = (numList1.pop() ?? 0) + (numList2.pop() ?? 0) + carry;
    carry = sum >= 10 ? Math.floor(sum / 10) : 0;
    const node = new ListNode(sum % 10);
    node.next = res;
    res = node;
  }
  return res;
};