[google面试CTCI] 2-4 计算两个单链表所代表的数之和
【链表】
Q:You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.
EXAMPLE
Input: (3 –> 1 –> 5), (5 –> 9 –> 2)
Output: 8 –> 0 –> 8
题目：给你两个由单链表表示的数，链表的每个节点代表一位数，计算两个数的和。
例如：
输入：(3 –> 1 –> 5), (5 –> 9 –> 2) （即513+292=808，注意个位数在链表头）
输出：8 –> 0 –> 8
解答：
方法一：既然我们知道每个链表代表一个数，那么我们先分别得到每个链表所代表的数，然后求和，再将和拆分成一位一位的数，最后将每一位作为链表的一个节点。但这样做有个问题就是，如果链表很长，超出了long int的表示范围，则得不到正确结果。即该方法不能用于计算大数。比如对于123466465464636543654365436+4134543543253432543254325这样的大数，此方法就无能为力了。
NODE* add_list(NODE* list1,NODE* list2){ int num1=0,num2=0,sum=0;//都用int类型，这里只为描述此方法的实现 int base=1; while(list1){//得到list1所代表的数字 num1+=(list1->data)*base; base*=10; list1=list1->next; } base=1; while(list2){//得到list2所代表的数字 num2+=(list2->data)*base; base*=10; list2=list2->next; } sum=num1+num2; NODE* List=init();//创建一个新的链表，链表创建见2-0节 if(List==NULL) return NULL; while(sum!=0){//将sum拆分，插入链表中 insert(List,sum%10); sum/=10; } return List;}方法二：针对方法一的缺点，我们自己对每一位进行相加，自己处理进位问题，这样带来的好处是不受链表长度的影响，我们可以完成任意大数的加法。每一次从链表中取一位，计算和及其进位，将和插入新链表，进位加入到下一位的计算中去。
NODE* add_list2(NODE* list1,NODE* list2){ if(list1==NULL) return list2; if(list2==NULL) return list1; int carry=0;//用来保存进位 int tmp=0; NODE * List=init(); NODE *p=list1; NODE *q=list2; while((p!=NULL)&& (q!=NULL)){//首先求两个链表共同长度部分的和 tmp=p->data+q->data+carry; insert(List,tmp%10); carry=tmp/10; p=p->next; q=q->next; } while(p!=NULL){//如果链表1比链表2长，将长出的部分加到新链表中取 tmp=p->data+carry; insert(List,tmp%10); carry=tmp/10; p=p->next; } while(q!=NULL){//如果链表2比链表1长，将长出的部分加到新链表中取 tmp=q->data+carry; insert(List,tmp%10); carry=tmp/10; q=q->next; } return List;}作者：Viidiot 微信公众号：linux-code