点击上方“蓝色字体”,选择“设为星标”
每天复习一道面试题,轻松拿大厂Offer~
给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807
2.addTwoNumbers
(图片来自:https://github.com/MisterBooo/LeetCodeAnimation)
,其中 N 的空间是调用栈的开销。
/**
* @来源: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++代码与上面的 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;
}
}
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;
}
}
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 操作。
由于单链表是线性的,使用递归方式将导致栈的使用也是线性的,当链表长度达到一定程度时,递归可能会导致爆栈,
// 普通递归
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);
}
};
关注公众号「IT平头哥联盟」,一起进步,一起成长!