CCI_Q2.4

本文参考该作者文章当作编程笔记：

作者：Hawstein
出处：http://hawstein.com/posts/ctci-solutions-contents.html

你有两个由单链表表示的数。每个结点代表其中的一位数字。数字的存储是逆序的，也就是说个位位于链表的表头。写一函数使这两个数相加并返回结果，结果也由链表表示。

例子：(3 -> 1 -> 5), (5 -> 9 -> 2)

输入：8 -> 0 -> 8

思路：

注意3点：两链表为空、两链表长度不一样、最后结果有进位。

CODE:

list.h可以参考CCI——Q2.3

客户程序：

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include"list.h"
 4 #define N 10
 5 struct node * addLink(link h1,link h2)
 6 {
 7     if(h1->next==NULL)return h2;
 8     if(h2->next==NULL)return h1;
 9     struct node *r;
10     int c=0;
11     initNodes(&r);
12     while(h1->next!=NULL&&h2->next!=NULL)
13     {
14         h1=Next(h1);h2=Next(h2);
15         int t=Item(h1)+Item(h2)+c;
16         c=t/10;t%=10;
17         insertNext(r,newNode(t));
18     }
19     while(h1->next!=NULL)
20     {
21         h1=Next(h1);
22         int t=Item(h1)+c;
23         c=t/10;t%=10;
24         insertNext(r,newNode(t));
25     }
26     while(h2->next!=NULL)
27     {
28         h2=Next(h2);
29         int t=Item(h2)+c;
30         c=t/10;t%=10;
31         insertNext(r,newNode(t));
32     }
33     if(c>0)
34     {
35         insertNext(r,newNode(c));
36     }
37     return r;
38 
39 }
40 void printfNodes(link h)
41 {
42     while(h->next!=NULL)
43     {
44         h=Next(h);
45         printf("%d	",Item(h));
46     }
47     printf("
");
48 }
49 int main()
50 {
51     struct node* head1,*head2;
52     initNodes(&head1);
53     initNodes(&head2);
54     int s[N]={8,4,2,8,7,2,3,7,8,9};
55     int i;
56     for(i=0;i<5;i++)
57         insertNext(head1,newNode(s[i]));
58     for(;i<N;i++)
59         insertNext(head2,newNode(s[i]));
60     link r=addLink(head1,head2);
61     printfNodes(r);
62     return 0;
63 }

问题：

程序是逆序插入数据的，所以结果是驴唇不对马嘴的。但是思路是对的。