[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