网站制作网页,多配色创意metro风格企业网站织梦模板,wordpress设置分类,阿里企业邮箱登陆入口LeetCode#xff1a;0002#xff08;两数之和#xff09; 题目描述#xff1a;给定两个非空链表来表示两个非负整数。位数按照逆序方式存储#xff0c;它们的每个节点只存储单个数字。将两数相加返回一个新的链表。你可以假设除了数字 0 之外#xff0c;这两个数字都不会… LeetCode0002两数之和 题目描述给定两个非空链表来表示两个非负整数。位数按照逆序方式存储它们的每个节点只存储单个数字。将两数相加返回一个新的链表。你可以假设除了数字 0 之外这两个数字都不会以零开头。示例输入(2 - 4 - 3) (5 - 6 - 4)输出7 - 0 - 8原因342 465 807 算法思路 思路 算法 就像你在纸上计算两个数字的和那样我们首先从最低有效位也就是列表 和 的表头开始相加。由于每位数字都应当处于 的范围内我们计算两个数字的和时可能会出现“溢出”。例如5 7 125712。在这种情况下我们会将当前位的数值设置为 2并将进位 带入下一次迭代。进位carry必定是0或1这是因为两个数字相加考虑到进位可能出现的最大和为 9 9 1 19。 伪代码如下 将当前结点初始化为返回列表的哑结点。将进位 carry初始化为0。将p和q分别初始化为列表和的头部。遍历列表和直至到达它们的尾端。 将x设为结点p的值。如果p已经到达$l1$的末尾则将其值设置为0。将y设为结点q的值。如果q已经到达l2的末尾则将其值设置为0。设定 $sum x y carry$。更新进位的值$carry sum / 10$。创建一个数值为 (sum mod 10) 的新结点并将其设置为当前结点的下一个结点然后将当前结点前进到下一个结点。同时将p和q前进到下一个结点。检查$carry 1$是否成立如果成立则向返回列表追加一个含有数字$11$的新结点。返回哑结点的下一个结点。解法 1/** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9class Solution {10public:11 ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {12 ListNode *dummyHead new ListNode(0);13 ListNode *cur dummyHead;14 int carry 0; //进位用15 while(l1 ! NULL || l2 ! NULL){16 int x (l1 ! NULL) ? l1 - val :0;17 int y ( l2 ! NULL) ? l2 - val : 0;18 int sum carry x y;19 carry sum / 10; //进位20 cur - next new ListNode(sum % 10); //指向下一节点21 cur cur - next;22 if(l1 ! NULL)23 l1 l1-next;24 if(l2 ! NULL)25 l2 l2-next;26 }27 if(carry0)28 cur-next new ListNode(carry); //加上进位29 return dummyHead-next;30 }31}; 转载于:https://www.cnblogs.com/ywx123/p/9971567.html
