Sum Lists: 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
1
2
|
Input: (7 -> 1 -> 6) + (5 -> 9 -> 2). That is, 617 + 295.
Output: 2 -> 1 -> 9. That is, 912.
|
FOLLOW UP
Suppose the digits are stored in forward order. Repeat the above problem.
EXAMPLE
1
2
|
lnput: (6 -> 1 -> 7) + (2 -> 9 -> 5). That is, 617 + 295.
Output: 9 -> 1 -> 2. That is, 912.
|
解法
这个问题还挺容易理解的，首先你得遍历这两个链表，然后在各自的位上相加，相加结果 mod 10，根据情况进一。遍历的时候注意一下两个链表长短不一致的问题。
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
|
public Node solve(Node a, Node b) {
Node head = new Node();
Node tail = head;
boolean plus1 = false;
while (a != null && b != null) {
int num = a.data + b.data;
num = plus1 ? num + 1 : num;
plus1 = num >= 10;
tail.next = new Node(num % 10);
tail = tail.next;
a = a.next;
b = b.next;
}
Node zero = new Node(0);
Node one = new Node(1);
if (a != null) {
// a比b长
tail.next = solve(a, plus1 ? one : zero);
} else if (b != null) {
// b比a长
tail.next = solve(b, plus1 ? one : zero);
} else if (plus1) {
// a、b一样长，但是有一个进位没有处理
tail.next = one;
}
return head.next;
}
|
解FOLLOW UP
FOLLOW UP是说把链表反过来了，那么第一个想到的就是把链表正过来，然后再用上面的办法解，最后再把结果反过来。不过这个似乎有点麻烦，要做3次反转，那么是不是有办法不需要反转就能计算呢？
能够想到的就是递归，即：
- 当前节点的结果+后面节点的数字=结果
- 如果后面节点要进1位，那么当前节点结果+1
还要处理两个链表长度不一致的问题，处理办法就是在前面补0。
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
|
@Override
public Node solve(Node a, Node b) {
int lengthA = length(a);
int lengthB = length(b);
if (lengthA > lengthB) {
b = leftPadZero(b, lengthA - lengthB);
}
if (lengthB > lengthA) {
a = leftPadZero(a, lengthB - lengthA);
}
Node result = new Node();
boolean plus1 = sum(result, a, b);
if (plus1) {
// 处理余下的进位
Node one = new Node(1);
one.next = result;
result = one;
}
return result;
}
// 计算长度
private int length(Node node) {
if (node == null) {
return 0;
}
return 1 + length(node.next);
}
// 左侧补齐0
private Node leftPadZero(Node node, int amount) {
if (amount == 0) {
return node;
}
Node head = node;
for (int i = 0; i < amount; i++) {
Node zero = new Node(0);
zero.next = head;
head = zero;
}
return head;
}
// a、b的长度都是一样的
private boolean sum(Node head, Node a, Node b) {
boolean plus1 = false;
if (a.next != null) {
head.next = new Node();
plus1 = sum(head.next, a.next, b.next);
}
int num = a.data + b.data;
num = plus1 ? num + 1 : num;
head.data = num % 10;
return num >= 10;
}
|
评论