/
QuestionB.java
89 lines (77 loc) · 2.4 KB
/
QuestionB.java
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
package Q2_05_Sum_Lists;
import CtCILibrary.LinkedListNode;
public class QuestionB {
private static int length(LinkedListNode l) {
if (l == null) {
return 0;
} else {
return 1 + length(l.next);
}
}
private static PartialSum addListsHelper(LinkedListNode l1, LinkedListNode l2) {
if (l1 == null && l2 == null) {
PartialSum sum = new PartialSum();
return sum;
}
PartialSum sum = addListsHelper(l1.next, l2.next);
int val = sum.carry + l1.data + l2.data;
LinkedListNode full_result = insertBefore(sum.sum, val % 10);
sum.sum = full_result;
sum.carry = val / 10;
return sum;
}
private static LinkedListNode addLists(LinkedListNode l1, LinkedListNode l2) {
int len1 = length(l1);
int len2 = length(l2);
if (len1 < len2) {
l1 = padList(l1, len2 - len1);
} else {
l2 = padList(l2, len1 - len2);
}
PartialSum sum = addListsHelper(l1, l2);
if (sum.carry == 0) {
return sum.sum;
} else {
LinkedListNode result = insertBefore(sum.sum, sum.carry);
return result;
}
}
private static LinkedListNode padList(LinkedListNode l, int padding) {
LinkedListNode head = l;
for (int i = 0; i < padding; i++) {
head = insertBefore(head, 0);
}
return head;
}
private static LinkedListNode insertBefore(LinkedListNode list, int data) {
LinkedListNode node = new LinkedListNode(data);
if (list != null) {
node.next = list;
}
return node;
}
public static int linkedListToInt(LinkedListNode node) {
int value = 0;
while (node != null) {
value = value * 10 + node.data;
node = node.next;
}
return value;
}
public static void main(String[] args) {
LinkedListNode lA1 = new LinkedListNode(3, null, null);
LinkedListNode lA2 = new LinkedListNode(1, null, lA1);
LinkedListNode lB1 = new LinkedListNode(5, null, null);
LinkedListNode lB2 = new LinkedListNode(9, null, lB1);
LinkedListNode lB3 = new LinkedListNode(1, null, lB2);
LinkedListNode list3 = addLists(lA1, lB1);
System.out.println(" " + lA1.printForward());
System.out.println("+ " + lB1.printForward());
System.out.println("= " + list3.printForward());
int l1 = linkedListToInt(lA1);
int l2 = linkedListToInt(lB1);
int l3 = linkedListToInt(list3);
System.out.print(l1 + " + " + l2 + " = " + l3 + "\n");
System.out.print(l1 + " + " + l2 + " = " + (l1 + l2));
}
}