2两数相加

Posted on
Words count in article: 1.2k | Reading time ≈ 5

两数相加I 和II

下面是题目I 和题目II

  • 这题比较折磨我，因为我一开始的思路，是用一个整型直接存储两个链表的数字，然后加起来，后来发现有类似于10000000000000这样的数据。让我不管取多大的，都会被越界。后来找了题解，给出几种解法

1-1利用位数补齐的方法。然后分别计算位数

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
//我们首先要明白l1，l2 都是倒序，所以补齐的时候只要再尾部插0就行了
//输出也是倒叙，所以从第一位开始加，进行计算就可以了
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int len1 = 1;
        int len2 = 1;
        ListNode *p1 = l1;
        ListNode *p2 = l2;
        //首先我们来计算位数！
        while(p1->next)
        {
            p1= p1->next;
            len1++;
        }
        while(p2->next)
        {
            p2 = p2->next;
            len2++;
        }
        //当l1比l2长的时候，在l2 后面补上0
        if(len1>len2)
        {
            for(int i = 1;i<=len1-len2;i++)
            {
                p2->next =new ListNode(0);
               p2 = p2 ->next;
            }
        }else//否则，就再l1 后面补0
        {
            for(int i = 1;i<=len2-len1;i++)
            {
                p1->next = new ListNode(0);
                p1= p1->next;
            }
        }
        p1= l1; p2 = l2;
        bool count = false;//count计算进位
        ListNode *l3 = new ListNode(-1);//新建链表
        ListNode *cur = l3;
        int i = 0;
        while(p1&&p2)
        {
            //对于每个位，都计算，注意，如果count为1，就说明上一位有进位，所以要加上1
            i = p1->val+p2->val+count;
            cur->next = new ListNode(i%10);
            count= i>=10? true:false;
            cur = cur->next;
            p1 = p1->next;
            p2 = p2->next;
        }
        //如果末位还有进位，那么要再尾插一个1，因为两<10整数相加最大为18
        if(count)
        {
            cur->next = new ListNode(1);
            cur = cur->next;
        }
        return l3->next;
    }
};

1-2 不使用补齐的方法，来试试

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
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *l3 =  new ListNode(-1);
        ListNode *cur = l3;
        int sum;
        bool count = false;
        //这里，让l1或者l2不为空，就进行操作
        //其余的方法，和补齐的一样
        while(l1||l2)
        {
            sum = 0;
            if(l1)
            {
                sum = sum+ l1->val;
                l1 = l1->next;
            }
            if(l2)
            {
                sum = sum+l2->val;
                l2 = l2->next;
            }
            if(count)
                sum++;
            cur->next = new ListNode(sum%10) ;
            count = sum>=10? true:false;
            cur = cur->next;
        }
        if(count)
            cur->next = new ListNode(1);
        return l3->next;
    }
};

2.两数相加II

这个题，用老思路也是可以做的，但是。。确实麻烦

  1. 反转两个链表
  2. 把两个链表安位次相加，得到新链表
  3. 把新链表反转后输出。
  4. 累死，还不一定对
  5. 但是，我们已经写好了反转链表的函数，和相加链表的函数。所以我们直接拿来用
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    //这是 206 反转链表的代码
    ListNode* reverseList(ListNode* head) {
        if (head == NULL || head->next == NULL) {
            return head;
        }
        ListNode* ret = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return ret;
    }
    //这是问题I中的代码
     ListNode* add_Two_Numbers(ListNode* l1, ListNode* l2) {
        ListNode *l3 =  new ListNode(-1);
        ListNode *cur = l3;
        int sum;
        bool count = false;
        while(l1||l2)
        {
            sum = 0;
            if(l1)
            {
                sum = sum+ l1->val;
                l1 = l1->next;
            }
            if(l2)
            {
                sum = sum+l2->val;
                l2 = l2->next;
            }
            if(count)
                sum++;
            cur->next = new ListNode(sum%10) ;
            count = sum>=10? true:false;
            cur = cur->next;
        }
        if(count)
            cur->next = new ListNode(1);
        return l3->next;
    }
    
    //最后来写II的代码，那就很简单了
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        //首先反转l1，l2
        l1 = reverseList(l1);
        l2 = reverseList(l2);
        //然后进行相加操作
        ListNode *head = add_Two_Numbers(l1,l2);
        l1 = reverseList(l1);
        l2  = reverseList(l2);
        //最后，把相加后的返回
        return reverseList(head);
    }

};

虽然上面思路简单，但是太过于笨重，下面用两个链表的新的栈来实现

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
 ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
	//首先，建立两个栈，然后把l1，l2 中的所有节点值入栈
    stack<int> stack1;
    while (l1)
    {
        stack1.push(l1->val);
        l1 = l1->next;
    }
    stack<int> stack2;
    while (l2)
    {
        stack2.push(l2->val);
        l2 = l2->next;
    }
    ListNode* temp = nullptr;
    ListNode* newList = nullptr;
    int carry = 0;
    //然后进行每个栈的top 元素相加
    while (!stack1.empty() || !stack2.empty())
    {
        int x = stack1.empty() ? 0 : stack1.top();
        int y = stack2.empty() ? 0 : stack2.top();
        if (!stack1.empty())
        {
            stack1.pop();
        }

        if (!stack2.empty())
        {
            stack2.pop();
        }

        int val = x + y + carry;
        carry = val / 10;//判断是否要进位
		//先让一个临时节点指向原节点
        temp= newList;
        //然后再新建一个节点，让他等于要头插的元素
        newList = new ListNode(val % 10);
        //最后让这个新的节点指向原链表
        newList->next = temp;
    }
	//如果最后一位要进1，再头插一个1
    if (carry == 1)
    {
        temp = newList;
        newList = new ListNode(1);
        newList->next = temp;
    }
	//最后返回新链表
    return newList;
}
};
-------------本文结束，感谢您的阅读-------------