黑龙江做网站的,教育行业网站制作,WordPress对接易支付,哪个网站买东西最便宜给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外#xff0c;这两个数字都不会以零开头。
示例1#xff1a;
输入#xff1a;l1 [7,2,4,3], l2 [5,6,4]…给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外这两个数字都不会以零开头。
示例1
输入l1 [7,2,4,3], l2 [5,6,4] 输出[7,8,0,7] 示例2
输入l1 [2,4,3], l2 [5,6,4] 输出[8,0,7] 示例3
输入l1 [0], l2 [0] 输出[0]
提示
链表的长度范围为 [1, 100] 0 node.val 9 输入数据保证链表代表的数字无前导 0
进阶如果输入链表不能翻转该如何解决 思路
先将两个输入的链表反转然后进行逐位相加最后将结果再反转回来。让最低位在前在相加过程中可以方便地处理进位问题。最后再将结果反转使得最高位在前满足题目要求。
在进行逐位相加的过程中代码中定义了一个新的链表用来存储相加的结果。在遍历输入的两个链表的过程中每次取出两个链表当前节点的值相加并加上新链表当前节点的值用于接收上一位的进位然后将相加的结果对10取余得到的值赋给新链表的当前节点将相加的结果除以10得到的值作为进位如果进位不为0则在新链表中添加一个新的节点用于存储这个进位。
在处理完两个链表共有的部分后如果两个链表的长度不等还需要将较长的链表剩余的部分也加到新链表中。这部分的处理逻辑和前面相同只是不再需要加两个链表的节点值只需要加上新链表当前节点的值接收上一位的进位。
最后将存储结果的新链表反转并返回。 AC代码
/** lc appleetcode.cn id445 langcpp** [445] 两数相加 II*/// lc codestart
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {ListNode* l3 new ListNode();ListNode* p3 l3;public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* rl1 reverse(l1);ListNode* rl2 reverse(l2);ListNode* p1 rl1;ListNode* p2 rl2;while (p1 ! nullptr p2 ! nullptr) {if (p3-next nullptr) {p3-next new ListNode();}p3 p3-next;int sum p1-val p2-val p3-val;int s sum % 10;int c sum / 10;p3-val s;if (c) {p3-next new ListNode(c);}p1 p1-next;p2 p2-next;}move(p1);move(p2);l3 l3-next;ListNode* rl3 reverse(l3);return rl3;}ListNode* reverse(ListNode* l) {ListNode* rl new ListNode();ListNode* p l;ListNode* rp;while (p ! nullptr) {rp new ListNode(p-val);rp-next rl-next;rl-next rp;p p-next;}rl rl-next;return rl;}void move(ListNode* p) {while (p ! nullptr) {if (p3-next nullptr) {p3-next new ListNode();}p3 p3-next;int sum p-val p3-val;int s sum % 10;int c sum / 10;p3-val s;if (c) {p3-next new ListNode(c);}p p-next;}}
};
// lc codeend
