2_两数相加

2. 两数相加

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

1
2
3


输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

思路：

主要考虑好相加进位问题，还有l1,l2不等长的处理

注意：

c++ struct的初始化应该这么写

1
2
3


ListNode* tmp = new ListNode(0);
//不要这么写,这么写不会new 一个新的listnode在循环里他们的地址都是一样的
ListNode tmp(0);

 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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89


//
//  main.cpp
//  leetcode_2
//
//  Created by 孙金辉 on 2019/3/21.
//  Copyright © 2019 孙金辉. All rights reserved.
//

#include <iostream>
#include <string>

using namespace std;

struct ListNode {
  int val;
  ListNode *next;
  ListNode(int x) : val(x), next(NULL) {}
};

ListNode* nextNode(ListNode* l){
    if (l != NULL && l->next != NULL) {
        l = l->next;
    }
    return l;
}

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode* ans_list =NULL;
//    ListNode* l1_head = l1;
//    ListNode* l2_head = l2;
    int add = 0;
    ListNode* tmp = new ListNode(0);
    ans_list = tmp;
    ListNode* p = ans_list;
    while (l1 != NULL) {
        ListNode *tmp = new  ListNode(add + l1->val);
        if (l2!= NULL ) {
            tmp->val += l2->val;
            l2 = l2->next;
        }
        add = tmp->val / 10;
        tmp->val = tmp->val % 10;
        l1 = l1->next;
        p->next = tmp;
        p = p->next;
    }
    while (l2 != NULL) {
        ListNode *tmp = new ListNode(l2->val+add);
        add = tmp->val/10;
        tmp->val = tmp->val%10;
        l2 = l2->next;
        p->next= tmp;
        p = p->next;
    }
    if (add != 0) {
        ListNode *tmp = new ListNode(add);
        p->next = tmp;
    }
    return ans_list->next;
}


int main(int argc, const char * argv[]) {
//    int a1[3] = {2,4,3};
//    int a2[3] = {5,6,4};
    int a1[3] = {5};
    int a2[3] = {5};
    ListNode head1(0);
    ListNode head2(0);
    ListNode* l1 = &head1;
    ListNode* l2 = &head2;
    ListNode *head_l1 = l1,*head_l2 = l2;

    for (int i = 0; i < 1; ++i) {
        ListNode *tmp1 = new ListNode(a1[i]);
        ListNode *tmp2 = new ListNode(a2[i]);
        l1->next = tmp1;
        l1 = l1->next;
        l2->next = tmp2;
        l2 = l2->next;
        
    }
    ListNode* ans = addTwoNumbers(head_l1->next, head_l2->next);
    while (ans != NULL) {
        cout << ans->val <<endl;
        ans = ans->next;
    }
    return 0;
}