2. 两数相加

题目描述

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

出处：LeetCode

解法一：模拟

思路

我们可以模拟两数相加的过程。我们定义一个哑节点 dummy，然后定义一个指针 prev 指向哑节点。然后我们遍历两个链表，每次迭代时，我们将两个链表的当前节点的值相加，然后将和的个位数作为新节点的值，将和的十位数作为进位。最后，如果进位不为 0，我们将进位加入到新链表的尾部。

实现

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  const dummy = new ListNode(0);
  let prev = dummy;
  let carry = 0;

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

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

    if (l1 !== null) {
      l1 = l1.next;
    }

    if (l2 !== null) {
      l2 = l2.next;
    }
  }

  if (carry !== 0) {
    prev.next = new ListNode(carry);
  }

  return dummy.next;
}

复杂度分析

• 时间复杂度：$O(\max(m, n))$，其中 $m$ 和 $n$ 分别是两个链表的长度。
• 空间复杂度：$O(\max(m, n))$，新链表的长度为 $\max(m, n) + 1$。

解法二：递归

思路

我们也可以使用递归来实现两数相加。我们定义一个递归函数 add，用来计算两个链表的和。在递归函数中，我们首先判断两个链表是否为空，如果两个链表都为空，则返回 null。然后我们计算两个链表的当前节点的和，然后递归地计算两个链表的下一个节点的和。最后，我们将两个链表的当前节点的和的个位数作为新节点的值，将和的十位数作为进位。

实现

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  return add(l1, l2, 0);
}

function add(l1: ListNode | null, l2: ListNode | null, carry: number): ListNode | null {
  if (l1 === null && l2 === null && carry === 0) {
    return null;
  }

  const val1 = l1 !== null ? l1.val : 0;
  const val2 = l2 !== null ? l2.val : 0;
  const sum = val1 + val2 + carry;

  const node = new ListNode(sum % 10);
  node.next = add(l1 !== null ? l1.next : null, l2 !== null ? l2.next : null, Math.floor(sum / 10));

  return node;
}

复杂度分析

• 时间复杂度：$O(\max(m, n))$，其中 $m$ 和 $n$ 分别是两个链表的长度。
• 空间复杂度：$O(\max(m, n))$，递归调用的深度为 $\max(m, n)$。