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 ;
}
评论