LeetCode 2. Add Two Numbers

LeetCode 2.png

问题描述

给定两个非空链表，每个链表表示一个正整数。数字以倒序的方式存储在链表中，且每个链表节点只包含单个数字。将两个整数相加，返回新的链表。

假定数字不会以 0 开头，除了 0 本身。

栗子：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8

解释：
由于数字是以倒序存储，则应该是 342 + 465 = 807.

想看英文原文的戳这里。

解题思路

思路比较明显，由于是倒序存储，也就是从低位开始。而两个数相加也是从低位开始计算，那么只需要同时遍历两个链表，求和两节点上的数字即可。

不过，要注意如下几点：

1. 两个链表的长度有可能不一样，需注意处理。
   假设当链表 l1 到末尾后，但链表 l2 还未到末尾，此时只需计算 l2 的值即可。

2. 处理进位问题。

   • 每位上的数字相加都要加上之前的进位。
   • 如果最长的链表遍历完成后，进位不为 0，则需添加新节点。

3. 使用虚拟头结点，插入操作更加简单。

下面记录下我的解法，一开始想复杂了🤩。

解法 1

1. 分别计算两个链表的长度，用来比较链表的长短。
2. 从较短的链表开始遍历，直到末尾。
3. 继续遍历较长的链表，直到末尾。
4. 处理最后的进位。

其实第 1 步完全没有必要。

解法 2

优化解法 1，去除第一步。

1. 同时遍历两个链表，直至短的链表遍历完成。此时还剩较长的链表需处理。
2. 继续遍历较长的链表，直至末尾。
3. 处理最后的进位。

解法 3

看了答案，要更加简洁一些。

1. 同时遍历两个链表，只要一个链表有值，就继续，直至所有节点都遍历完成。如果链表节点有值，就累加到结果中求和。
2. 处理最后进位。

js 代码实现如下：

var addTwoNumbers3 = function (l1, l2) {

  // 虚拟节点
  let result = new ListNode(0, null)
  let tmp = result

  // 进位
  let c = 0

  // 遍历链表
  while (l1 || l2) {
    let sum = 0
    if (l1) {
      sum += l1.val
    }

    if (l2) {
      sum += l2.val
    }

    const n = sum + c

    // 进位
    c = Math.floor(n / 10)

    const val = n % 10
    const node = new ListNode(val, null)

    // 插入节点
    tmp.next = node
    tmp = node

    if (l1) {
      l1 = l1.next
    }

    if (l2) {
      l2 = l2.next
    }
  }

  // 最高位有进位，需生成新节点
  if (c > 0) {
    const node = new ListNode(c, null)
    tmp.next = node
  }

  return result.next
};