链表 2.5

给定两个用链表表示的整数，每个结点包含一个数位。这些数位是反向存放的，也就是个位排在链表首部。编写函数对这两个整数求和，并用链表形式返回结果。

示例

输入：( 7 -> 1 -> 6 ) + ( 5 -> 9 -> 2 )，即 617 + 295

输出：2 -> 1 -> 9，即 912

进阶

假设这些数位是正向存放的，请再做一遍。

示例

输入：( 6 -> 1 -> 7 ) + ( 2 -> 9 -> 5 )，即 617 + 295

输出：9 -> 1 -> 2，即 912

分析：因为数位是反向存放的，因此从低位往高位逐位相加即可。需要注意进位和两个数的长度不匹配的情况。

 1 //struct Node {
 2 //    Node(): val(0), next(0) {}
 3 //    Node( int value ): val(value), next(0) {}
 4 //    int val;
 5 //    Node *next;
 6 //};
 8 Node *addList( Node *num1, Node *num2 ) {
 9     Node guard, *node = &guard;
10     int carry = 0;
11     while( num1 || num2 ) {
12         if( num1 ) {
13             carry += num1->val;
14             num1 = num1->next;
15         }
16         if( num2 ) {
17             carry += num2->val;
18             num2 = num2->next;
19         }
20         node->next = new Node( carry%10 );
21         node = node->next;
22         carry /= 10;
23     }
24     if( carry ) { node->next = new Node( carry ); }
25     return guard.next;
26 }

对于进阶中的情况，我们只需先将输入数据反转，然后求和，再将结果反转即可。反转链表代码如下：

 1 Node *reverseList( Node *head ) {
 2     if( !head ) { return 0; }
 3     Node *node = head->next;
 4     head->next = 0;
 5     while( node ) {
 6         Node *next = node->next;
 7         node->next = head;
 8         head = node;
 9         node = next;
10     }
11     return head;
12 }

运行结果

num1: ""
num2: ""
sum: ""
"" + "" = ""

num1: ""
num2: 1
sum: 1
"" + 1 = 1

num1: ""
num2: 1->2
sum: 1->2
"" + 21 = 21

num1: 1
num2: 1->2
sum: 2->2
1 + 21 = 22

num1: 1->2
num2: 6->9
sum: 7->1->1
21 + 96 = 117

num1: 6->5
num2: 1->4->6->9
sum: 7->9->6->9
56 + 9641 = 9697