[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;
}

补充：综合编程 , 其他综合 ,