leetcode#2
2019-05-22 / Luo Jinrong   

题目描述

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

1
2
3
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
  • 求解方法
  • 按照小学数学中的加法方法，从两数个位开始加，并设置一个变量来记录进位信息。
  • 代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int flag=0;//记录进位
        ListNode *ans=NULL,*tail=NULL;//ans为头节点，tail为尾节点
        for(ListNode *tmp1=l1,*tmp2=l2;tmp1!=NULL||tmp2!=NULL;){//循环直到两个数都加到最高位
            if(tmp1!=NULL&&tmp2!=NULL){//两个数该位都还有值
                if(tail==NULL){//当前位为个位
                    ans=new ListNode(tmp1->val+tmp2->val+flag);//为答案位申请一位空间
                    tail=ans;
                    if(tail->val>=10){//发生进位
                        tail->val-=10;
                        flag=1;
                    }
                    else{//没有进位
                        flag=0;
                    }
                }
                else{//不是个位
                    tail->next=new ListNode(tmp1->val+tmp2->val+flag);
                    tail=tail->next;
                    if(tail->val>=10){
                        tail->val-=10;
                        flag=1;
                    }
                    else{
                        flag=0;
                    }
                }
                tmp1=tmp1->next;//计算下一位
                tmp2=tmp2->next;
            }
            else if(tmp1==NULL){//tmp1计算完了
                tail->next=new ListNode(tmp2->val+flag);
                tail=tail->next;
                if(tail->val>=10){
                    tail->val-=10;
                    flag=1;
                }
                else{
                    flag=0;
                }
                tmp2=tmp2->next;
            }
            else if(tmp2==NULL){//tmp2计算完了
                tail->next=new ListNode(tmp1->val+flag);
                tail=tail->next;
                if(tail->val>=10){
                    tail->val-=10;
                    flag=1;
                }
                else{
                    flag=0;
                }
                tmp1=tmp1->next;
            }
        }
        if(flag){//如果进位还为1，则再申请一位
            tail->next=new ListNode(flag);
            tail=tail->next;
        }
        return ans;
    }
};

return 0;

本文链接：
https://luojinrong.github.io/2019/05/22/leetcode-2/