LeetCode 2. Add Two Numbers

liu_liu

关注

发布于: 2020 年 06 月 21 日

问题描述

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

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

栗子：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)输出：7 -> 0 -> 8
解释：由于数字是以倒序存储，则应该是 342 + 465 = 807.

复制代码

想看英文原文的戳这里。

解题思路

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

不过，要注意如下几点：

两个链表的长度有可能不一样，需注意处理。

假设当链表 l1 到末尾后，但链表 l2 还未到末尾，此时只需计算 l2 的值即可。

处理进位问题。

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

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

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

解法 1

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

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

解法 2

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

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

解法 3

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

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

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};

复制代码

发布于: 2020 年 06 月 21 日阅读数: 52

原文链接:【http://xie.infoq.cn/article/bf820e0bf67b99f8ad5e3f392】。文章转载请联系作者。

liu_liu

关注

不要相信自己的记忆力 2017.11.13 加入

还未添加个人简介

发布

暂无评论

创作场景

LeetCode 2. Add Two Numbers

问题描述

解题思路

解法 1

解法 2

解法 3

liu_liu

评论