Leetcode:0002(两数之和)

LeetCode:0002(两数之和)

题目描述:给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
你可以假设除了数字 0 之外,这两个数字都不会以零开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807

算法思路

思路

Leetcode:0002(两数之和)
算法
  就像你在纸上计算两个数字的和那样,我们首先从最低有效位也就是列表 Leetcode:0002(两数之和)Leetcode:0002(两数之和)的表头开始相加。由于每位数字都应当处于 Leetcode:0002(两数之和) 的范围内,我们计算两个数字的和时可能会出现“溢出”。例如,5 + 7 = 125+7=12。在这种情况下,我们会将当前位的数值设置为 2,并将进位 Leetcode:0002(两数之和) 带入下一次迭代。进位carry必定是0或1,这是因为两个数字相加(考虑到进位)可能出现的最大和为 9 + 9 + 1 = 19。

伪代码如下:

  • 将当前结点初始化为返回列表的哑结点。
  • 将进位 carry初始化为0。
  • 将p和q分别初始化为列表Leetcode:0002(两数之和)Leetcode:0002(两数之和)的头部。
  • 遍历列表Leetcode:0002(两数之和)Leetcode:0002(两数之和)直至到达它们的尾端。
    • 将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(carry>0)
28            cur->next = new ListNode(carry);    //加上进位
29        return dummyHead->next;
30    }
31};
上一篇:PHP调试工具 《Kint》


下一篇:从原理上搞定编码(二)-- Web编码