首页 > 代码库 > 链表 2.5
链表 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: 1sum: 1"" + 1 = 1num1: ""num2: 1->2sum: 1->2"" + 21 = 21num1: 1num2: 1->2sum: 2->21 + 21 = 22num1: 1->2num2: 6->9sum: 7->1->121 + 96 = 117num1: 6->5num2: 1->4->6->9sum: 7->9->6->956 + 9641 = 9697
链表 2.5
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。