题目
原文:
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)
输入:8 -> 0 -> 8
解答
这道题目并不难,需要注意的有:1.链表为空。2.有进位。3.链表长度不一样。 代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
using namespace std;
typedef struct node{
int data;
node *next;
}node;
node* init(int a[], int n){
node *head=NULL, *p;
for(int i=0; i<n; ++i){
node *nd = new node();
nd->data = a[i];
if(i==0){
head = p = nd;
continue;
}
p->next = nd;
p = nd;
}
return head;
}
node* addlink(node *p, node *q){
if(p==NULL) return q;
if(q==NULL) return p;
node *res, *pre=NULL;
int c = 0;
while(p && q){
int t = p->data + q->data + c;
node *r = new node();
r->data = t%10;
if(pre){
pre->next = r;
pre = r;
}
else pre = res = r;
c = t/10;
p = p->next; q = q->next;
}
while(p){
int t = p->data + c;
node *r = new node();
r->data = t%10;
pre->next = r;
pre = r;
c = t/10;
p = p->next;
}
while(q){
int t = q->data + c;
node *r = new node();
r->data = t%10;
pre->next = r;
pre = r;
c = t/10;
q = q->next;
}
if(c>0){//当链表一样长,而又有进位时
node *r = new node();
r->data = c;
pre->next = r;
}
return res;
}
void print(node *head){
while(head){
cout<<head->data<<" ";
head = head->next;
}
cout<<endl;
}
int main(){
int n = 4;
int a[] = {
1, 2, 9, 3
};
int m = 3;
int b[] = {
9, 9, 2
};
node *p = init(a, n);
node *q = init(b, m);
node *res = addlink(p, q);
if(p) print(p);
if(q) print(q);
if(res) print(res);
return 0;
}
全书题解目录:
Cracking the coding interview–问题与解答
全书的C++代码托管在Github上:
https://github.com/Hawstein/cracking-the-coding-interview
声明:自由转载-非商用-非衍生-保持署名 | 创意共享3.0许可证,转载请注明作者及出处
出处:http://hawstein.com/2012/12/16/2.4/