Day10-Task2.两数相加
程序员文章站
2024-03-15 23:43:12
...
题目描述
2.两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807
解题思路
和全加器原理类似,设立本位和 sum 和进位 co。
令初始进位 co = 0
每个节点 val 分别为 x,y
则本位和为本位数值相加再加上进位y
sum = x + y + co
解题过程中需要注意的是两链表长度可能不相等,因此应注意 x,y 在什么时候取 0 。
此外还应注意,若两链表长度相等,最后一节点相加时 x + y > 10 产生进位,因此在循环外应单独判断最后一结点相加完后 co 是否等于 1
时间复杂度 O(n)
代码如下
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* p = new ListNode(-1);
ListNode* ans = p;
int co = 0; //进位符
while(l1 != NULL || l2 != NULL)
{
int x, y;
if(l1 != NULL)
{
x = l1->val;
l1 = l1->next;
}
else
{
x = 0;
}
if(l2 != NULL)
{
y = l2->val;
l2 = l2->next;
}
else
{
y = 0;
}
int sum = x + y + co;
p->next = new ListNode(sum%10);
p = p->next;
co = sum/10;
}
if(co == 1)
p->next = new ListNode(1);
return ans->next;
}
};
执行结果
推荐阅读
-
Day10-Task2.两数相加
-
Task10.两数相加
-
刻意练习:LeetCode实战 -- Task10. 两数相加
-
【leetcode刷题日记】Task10-两数相加
-
LeetCode Task10.两数相加
-
给定一个数组, 求如果排序之后, 相邻两数的最大差值, 要求时 间复杂度O(N), 且要求不能用非基于比较的排序。
-
【算法】给定一个数组,求如果排序之后,相邻两数的最大差值,要求时间复杂度O(N),且要求不能用非基于比较的排序
-
给定一个数组,求如果排序之后,相邻两数的的最大差值(Java实现)
-
【左神算法】给定一个数组,求如果排序之后,相邻两数的最大差值,要求时间复杂度O(N),且要求不能用非基于比较的排序。
-
给定一个数组,求如果排序之后,相邻两数的最大差值,要求时 间复杂度O(N),且要求不能用非基于比较的排序