LeetCode 2. Add Two Numbers

发布于: 2020 年 06 月 21 日
LeetCode 2. Add Two Numbers

问题描述

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

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

栗子:

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

想看英文原文的戳这里

解题思路

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

不过,要注意如下几点:

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

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

  1. 处理进位问题。

  • 每位上的数字相加都要加上之前的进位。

  • 如果最长的链表遍历完成后,进位不为 0,则需添加新节点。

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

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

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

发布于: 2020 年 06 月 21 日 阅读数: 5
用户头像

liu_liu

关注

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

还未添加个人简介

评论

发布
暂无评论
LeetCode 2. Add Two Numbers