☆打卡算法☆LeetCode 2、两数相加 算法解析
一、题目
1、算法题目
“将两个链表中的数字组合成两个数，两个数相加，并返回一个相同格式的表示和的链表。”
题目链接： 来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers/
2、题目描述
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
比如：
l1 = [1,2,3],l2 = [4,5,6] 输出：[9,7,5] 因为321 + 654 = 975 ，返回 [9,7,5] 。
二、解题
1、思路分析
这道题是算两个链表组成的数的和，所以首先在较短的链表后面补零让两个链表的位数补齐，再将链表中的元素相加，还要考虑进位问题。
2、代码实现
假设当前两个链表处相应位置的数字为n1,n2,进位值为carry，则它们的和为newVal=n1+n2+carry;
那么答案链表新的进位值为(n1 + n2 + carry) / 10 也就是 carry = newVal / 10; 那么答案链表的对应位置的数字为n1 + n2 + carry % 10 也就是 newVal %= 10;
public class Solution
{
public ListNode AddTwoNumbers(ListNode l1, ListNode l2)
{
ListNode p1 = l1, p2 = l2;
ListNode dummy = new ListNode(-1);
ListNode p = dummy;
int carry = 0, newVal = 0;
while (p1 != null || p2 != null || carry > 0)
{
newVal = (p1 == null ? 0: p1.val) + (p2 == null ? 0: p2.val) + carry;
carry = newVal / 10;
newVal %= 10;
p.next = new ListNode(newVal);
p1 = p1 == null? null: p1.next;
p2 = p2 == null? null: p2.next;
p = p.next;
}
return dummy.next;
}
} 执行结果：
image.png
3、时间复杂度
时间复杂度：O(max(m,n))
m和n是两个链表的长度。要遍历两个链表的全部位置，而每个位置只需要O(1)的时间。
空间复杂度：O(1)
三、总结
这道题难度中等，对于新学习算法的人来说还是有点难度的。
按顺序刷题的在默哀。。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021-09-26，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
