You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 –> 8
大整数加法
|
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 |
/** * 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
carryBit = 0; ListNode tmpHead(0), *res = &tmpHead; while(l1 && l2) { l1->val += (l2->val + carryBit); carryBit = l1->val / 10; l1->val %= 10; res->next = l1; res = l1; l1 = l1->next; l2 = l2->next; } ListNode *p = (l1 == NULL ? l2 : l1); //此时l1,l2至多一个不为NULL while(p) { if(carryBit == 0) { res->next = p; break; } else { p->val += carryBit; carryBit = p->val / 10; p->val %= 10; res->next = p; res = p; } p = p->next; } if(carryBit != 0)res->next = new
ListNode(carryBit); return
tmpHead.next; }}; |
如果链表存储整数时，高位在前，该如何处理。
1、最简单的想法是，可以先把链表反转，然后调用上面的算法，最后把结果反转。
2、可不可以从高位向低位方向处理呢？我们知道进位是从低位传向高位的，如果从高位向低位方向计算，当计算到某一位需要进位时，有没有办法知道该进位传递到前面的哪一位呢？从以下几个例子来看：
从最高位到最低位我们依次记为第 1,2…,7位。图中红色标记的位置是：下一次需要进位时，进位的1放置的位子
第1位相加，结果为12，需要进位，这个进位放到第0位；同时标记第1位为下一次的进位标志
第2位相加，结果为3，不需要进位；标记第2位为下一次进位标志
第3位相加，结果为3，不需要进位；标记第3位为下一次进位标志
第4位相加，结果为9，不需要进位；此时进位标志不需要移动，因为9加上一个进位后还要继续向前进位
第5位相加，结果为9，不需要进位；此时进位标志不需要移动，因为9加上一个进位后还要继续向前进位
第6位相加，结果为14，需要进位，这个进位放到前面标记的第3位上，同时把第4位和第5位置0，标记第6位为下一次进位标志
第7位同上
所以综上所述，从高位往低位计算加法时，规则是：
一、如果当前位没有进位：（1）如果当前位的和小于9，则把改位设置成下一次进位标志（2）如果和等于9，进位标志不变
二、如果当前位有进位：把进位的1加到前面标志的位子上，同时把标志位和当前位之间的位全部置0（因为他们之间的位肯定全部都是9），把当前位设置成进位标志
上面我们举例的两个加数长度一致，如果长度不相同，则要先处理较长的整数的前面多出的部分。
我们把这一题leetcode的输入反转，测试代码如下：
|
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 |
/** * 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) { l1 = reverseList(l1); l2 = reverseList(l2); int
n1 = lenList(l1), n2 = lenList(l2); if(n1 < n2)//l1 指向较长的链表 { swap(n1,n2); swap(l1,l2); } //carryLoc是下一次出现进位时，进位的1将要放置的位子，pre指向当前结果链表的最后一个节点 //p1,p2分别是当前处理的l1,l2节点 //由于加数的最高位有可能进位，所以添加一个新的节点newHead ListNode *newHead = new
ListNode(0), *carryLoc = newHead, *pre = newHead, *p1 = l1; for(int
i = 0; i < n1-n2; i++)//处理l1高位长出的部分 { if(p1->val < 9)carryLoc = p1; pre->next = p1; pre = p1; p1 = p1->next; } ListNode* p2 = l2; while(p1 != NULL) { pre->next = p1; pre = p1; p1->val += p2->val; if(p1->val > 9) { carryLoc->val += 1; for(carryLoc = carryLoc->next; carryLoc != p1; carryLoc = carryLoc->next)//carryLoc到p1之间的节点全部置0 carryLoc->val = 0; p1->val -= 10; } if(p1->val < 9) carryLoc = p1; p1 = p1->next; p2 = p2->next; } if(newHead->val != 0)return
reverseList(newHead); else
return reverseList(newHead->next); } //反转链表 ListNode *reverseList(ListNode *l1) { ListNode *p = l1->next, *pre = l1; l1->next = NULL; while(p) { ListNode *tmp = p->next; p->next = pre; pre = p; p = tmp; } return
pre; } //求链表长度 int
lenList(ListNode *head) { int
res = 0; while(head) { res++; head = head->next; } return
res; }}; |
【版权声明】转载请注明出处：http://www.cnblogs.com/TenosDoIt/p/3735362.html
LeetCode:Add Two Numbers,布布扣,bubuko.com
原文：http://www.cnblogs.com/TenosDoIt/p/3735362.html