其他
002. 两数相加 | Leetcode题解
点击上方“蓝色字体”，选择“设为星标”
每天复习一道面试题，轻松拿大厂Offer~
题目描述
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
难度：
难度：中等 支持语言：JavaScript、Java、Python、C++
相关标签
链表 数学
相关企业
阿里 百度 腾讯
思路与算法
设立一个表示进位的变量 carried，建立一个新链表，把输入的两个链表从头往后同时处理，每两个相加，将结果加上 carried 后的值作为一个新节点到新链表后面，并更新 carried 值即可。
(图片来自：https://github.com/MisterBooo/LeetCodeAnimation)
实际上两个大数相加也是一样的思路， 只不过具体的操作 API 不一样而已。这种题目思维难度不大，难点在于心细，因此大家一定要自己写一遍，确保 bug free。
由于输入的两个链表都是逆序存储数字的位数的，因此两个链表中同一位置的数字可以直接相加。
我们同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。具体而言，如果当前两个链表处相应位置的数字为 n1,n2n1,n2，进位值为 \textit{carry}carry，则它们的和为 n1+n2+\textit{carry}n1+n2+carry；其中，答案链表处相应位置的数字为 (n1+n2+\textit{carry}) % 10(n1+n2+carry)%10，而新的进位值为 \lfloor\frac{n1+n2+\textit{carry}}{10}\rfloor⌊ 10 n1+n2+carry ⌋。
如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个 00 。
此外，如果链表遍历结束后，有 \textit{carry} > 0carry>0，还需要在答案链表的后面附加一个节点，节点的值为 \textit{carry}carry。
关键点解析
链表这种数据结构的特点和使用
用一个 carried 变量来实现进位的功能，每次相加之后计算 carried，并用于下一位的计算
复杂度分析
时间复杂度： 空间复杂度：，其中 N 的空间是调用栈的开销。 空间复杂度：O(\max(m,n))O(max(m,n))。答案链表的长度最多为较长链表的长度 +1+1。
代码
JavaScript 实现
/**
* @来源：Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍：前端中文网是以前端进阶资源教程分享为主的专业网站，包括：前端、大厂面试题、typescript教程、程序人生、React.js
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function (l1, l2) {
if (l1 === null || l2 === null) return null;
// 使用dummyHead可以简化对链表的处理，dummyHead.next指向新链表
let dummyHead = new ListNode(0);
let cur1 = l1;
let cur2 = l2;
let cur = dummyHead; // cur用于计算新链表
let carry = 0; // 进位标志
while (cur1 !== null || cur2 !== null) {
let val1 = cur1 !== null ? cur1.val : 0;
let val2 = cur2 !== null ? cur2.val : 0;
let sum = val1 + val2 + carry;
let newNode = new ListNode(sum % 10); // sum%10取模结果范围为0~9，即为当前节点的值
carry = sum >= 10 ? 1 : 0; // sum>=10，carry=1，表示有进位
cur.next = newNode;
cur = cur.next;
if (cur1 !== null) {
cur1 = cur1.next;
}
if (cur2 !== null) {
cur2 = cur2.next;
}
}
if (carry > 0) {
// 如果最后还有进位，新加一个节点
cur.next = new ListNode(carry);
}
return dummyHead.next;
};
/**
* @作者：LeetCode-Solution
* @链接：https://leetcode-cn.com/problems/add-two-numbers/solution/liang-shu-xiang-jia-by-leetcode-solution/
*/
var addTwoNumbers = function(l1, l2) {
let head = null, tail = null;
let carry = 0;
while (l1 || l2) {
const n1 = l1 ? l1.val : 0;
const n2 = l2 ? l2.val : 0;
const sum = n1 + n2 + carry;
if (!head) {
head = tail = new ListNode(sum % 10);
} else {
tail.next = new ListNode(sum % 10);
tail = tail.next;
}
carry = Math.floor(sum / 10);
if (l1) {
l1 = l1.next;
}
if (l2) {
l2 = l2.next;
}
}
if (carry > 0) {
tail.next = new ListNode(carry);
}
return head;
};
/**
* @作者：afeng-xiu - 力扣（LeetCode）
* @链接：https://leetcode-cn.com/problems/add-two-numbers/solution/liang-ge-shu-xiang-jia-zui-rong-yi-li-jie-de-jie-f/
*/
var addTwoNumbers = function(l1, l2) {
let addOne = 0
let sum = new ListNode('0')
let head = sum
while (addOne || l1 || l2) {
let val1 = l1 !== null ? l1.val : 0 // 优化点
let val2 = l2 !== null ? l2.val : 0 //优化点
let r1 = val1 + val2 + addOne
addOne = r1 >= 10 ? 1 : 0
sum.next = new ListNode(r1 % 10)
sum = sum.next
if (l1) l1 = l1.next
if (l2) l2 = l2.next
}
return head.next
};
C++ 实现:
C++代码与上面的 JavaScript 代码略有不同：将 carry 是否为 0 的判断放到了 while 循环中
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* ret = nullptr;
ListNode* cur = nullptr;
int carry = 0;
while (l1 != nullptr || l2 != nullptr || carry != 0) {
carry += (l1 == nullptr ? 0 : l1->val) + (l2 == nullptr ? 0 : l2->val);
auto temp = new ListNode(carry % 10);
carry /= 10;
if (ret == nullptr) {
ret = temp;
cur = ret;
}
else {
cur->next = temp;
cur = cur->next;
}
l1 = l1 == nullptr ? nullptr : l1->next;
l2 = l2 == nullptr ? nullptr : l2->next;
}
return ret;
}
};
/**
* @作者：chenlele
* @链接：https://leetcode-cn.com/problems/add-two-numbers/solution/liang-shu-xiang-jia-by-gpe3dbjds1/
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int len1=1;//记录l1的长度
int len2=1;//记录l2的长度
ListNode* p=l1;
ListNode* q=l2;
while(p->next!=NULL)//获取l1的长度
{
len1++;
p=p->next;
}
while(q->next!=NULL)//获取l2的长度
{
len2++;
q=q->next;
}
if(len1>len2)//l1较长，在l2末尾补零
{
for(int i=1;i<=len1-len2;i++)
{
q->next=new ListNode(0);
q=q->next;
}
}
else//l2较长，在l1末尾补零
{
for(int i=1;i<=len2-len1;i++)
{
p->next=new ListNode(0);
p=p->next;
}
}
p=l1;
q=l2;
bool count=false;//记录进位
ListNode* l3=new ListNode(-1);//存放结果的链表
ListNode* w=l3;//l3的移动指针
int i=0;//记录相加结果
while(p!=NULL&&q!=NULL)
{
i=count+p->val+q->val;
w->next=new ListNode(i%10);
count=i>=10?true:false;
w=w->next;
p=p->next;
q=q->next;
}
if(count)//若最后还有进位
{
w->next=new ListNode(1);
w=w->next;
}
return l3->next;
}
};
/**
* @作者：dnanki
* @链接：https://leetcode-cn.com/problems/add-two-numbers/solution/di-gui-si-lu-jian-dan-dai-ma-duan-by-dnanki/
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
return dfs(l1, l2, 0);
}
ListNode dfs(ListNode l, ListNode r, int i) {
if (l == null && r == null && i == 0) return null;
int sum = (l != null ? l.val : 0) + (r != null ? r.val : 0) + i;
var node = new ListNode(sum % 10);
node.next = dfs(l != null ? l.next : null, r != null ? r.next : null, sum / 10);
return node;
}
}
Java 实现:
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0);
ListNode cur = dummyHead;
int carry = 0;
while(l1 != null || l2 != null)
{
int sum = carry;
if(l1 != null)
{
sum += l1.val;
l1 = l1.next;
}
if(l2 != null)
{
sum += l2.val;
l2 = l2.next;
}
// 创建新节点
carry = sum / 10;
cur.next = new ListNode(sum % 10);
cur = cur.next;
}
if (carry > 0) {
cur.next = new ListNode(carry);
}
return dummyHead.next;
}
}
/**
* @作者：Sophia_fez
* @链接：https://leetcode-cn.com/problems/add-two-numbers/solution/mo-ni-jia-fa-tong-yong-mo-ban-by-sophia_fez/
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = new ListNode(0), cur = head;
int carry = 0;
while (l1 != null || l2 != null) {
int n1 = l1 != null ? l1.val : 0;
int n2 = l2 != null ? l2.val : 0;
int sum = n1 + n2 + carry;
carry = sum / 10;
cur.next = new ListNode(sum % 10);
cur = cur.next;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
if (carry > 0) cur.next = new ListNode(carry);
return head.next;
}
}
Python 实现:
class Solution:
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
res=ListNode(0)
head=res
carry=0
while l1 or l2 or carry!=0:
sum=carry
if l1:
sum+=l1.val
l1=l1.next
if l2:
sum+=l2.val
l2=l2.next
# set value
if sum<=9:
res.val=sum
carry=0
else:
res.val=sum%10
carry=sum//10
# creat new node
if l1 or l2 or carry!=0:
res.next=ListNode(0)
res=res.next
return head
# @作者：meng-zhi-hen-n
# @链接：https://leetcode-cn.com/problems/add-two-numbers/solution/zui-zhi-bai-de-xie-fa-by-meng-zhi-hen-n-2/
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
# 创建一个结点值为 None 的头结点, dummy 和 p 指向头结点, dummy 用来最后返回, p 用来遍历
dummy = p = ListNode(None)
s = 0 # 初始化进位 s 为 0
while l1 or l2 or s:
# 如果 l1 或 l2 存在, 则取l1的值 + l2的值 + s(s初始为0, 如果下面有进位1, 下次加上)
s += (l1.val if l1 else 0) + (l2.val if l2 else 0)
p.next = ListNode(s % 10) # p.next 指向新链表, 用来创建一个新的链表
p = p.next # p 向后遍历
s //= 10 # 有进位情况则取模, eg. s = 18, 18 // 10 = 1
l1 = l1.next if l1 else None # 如果l1存在, 则向后遍历, 否则为 None
l2 = l2.next if l2 else None # 如果l2存在, 则向后遍历, 否则为 None
return dummy.next # 返回 dummy 的下一个节点, 因为 dummy 指向的是空的头结点, 下一个节点才是新建链表的后序节点
拓展
通过单链表的定义可以得知，单链表也是递归结构，因此，也可以使用递归的方式来进行 reverse 操作。
由于单链表是线性的，使用递归方式将导致栈的使用也是线性的，当链表长度达到一定程度时，递归可能会导致爆栈，
算法
将两个链表的第一个节点值相加，结果转为 0-10 之间的个位数，并设置进位信息 将两个链表第一个节点以后的链表做带进位的递归相加 将第一步得到的头节点的 next 指向第二步返回的链表
C++实现
// 普通递归
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
return addTwoNumbers(l1, l2, 0);
}
private:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2, int carry) {
if (l1 == nullptr && l2 == nullptr && carry == 0) return nullptr;
carry += (l1 == nullptr ? 0 : l1->val) + (l2 == nullptr ? 0 : l2->val);
auto ret = new ListNode(carry % 10);
ret->next = addTwoNumbers(l1 == nullptr ? l1 : l1->next,
l2 == nullptr ? l2 : l2->next,
carry / 10);
return ret;
}
};
// 类似尾递归
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* head = nullptr;
addTwoNumbers(head, nullptr, l1, l2, 0);
return head;
}
private:
void addTwoNumbers(ListNode*& head, ListNode* cur, ListNode* l1, ListNode* l2, int carry) {
if (l1 == nullptr && l2 == nullptr && carry == 0) return;
carry += (l1 == nullptr ? 0 : l1->val) + (l2 == nullptr ? 0 : l2->val);
auto temp = new ListNode(carry % 10);
if (cur == nullptr) {
head = temp;
cur = head;
} else {
cur->next = temp;
cur = cur->next;
}
addTwoNumbers(head, cur, l1 == nullptr ? l1 : l1->next, l2 == nullptr ? l2 : l2->next, carry / 10);
}
};
其他
说明：[leetcode 题解 | 每日一题🔥] 所有题目并非全部为本人解答，部分为在复习学习中整理提取其他解题作者的优秀笔记，便于大家学习共同进步，如有侵权，请联系删除。 合作方：JavaScript中文网 – 全球极客挚爱的技术成长平台 原题leetcode链接：2.add-two-numbers](https://leetcode-cn.com/problems/add-two-numbers/) - 完 -