PROBLEM DESCRIPTION
Given two numbers, num1, and num2, represented by linked lists. The task is to return the head of the linked list representing the sum of these two numbers.
For example, the number 190 will be represented by the linked list, 1->9->0->null, similarly 25 by 2->5->null. Sum of these two numbers is 190 + 25 = 215, which will be represented by 2->1->5->null. You are required to return the head of the linked list 2->1->5->null.
Note: There can be leading zeros in the input lists, but there should not be any leading zeros in the output list.
SOLUTION
Reverse the given lists to make it simpler to evaluate the answer. Take one node at a time and calculate the current digit in the answer and carry. Stop when the digits exhaust and carry becomes 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
56
57
58
class Solution {
static Node addTwoLists(Node num1, Node num2) {
num1 = reverseLinkedList(num1);
num2 = reverseLinkedList(num2);
int carry = 0;
Node list = null;
Node h1 = num1;
Node h2 = num2;
while(h1 != null || h2 != null || carry != 0){
int d1 = h1 == null ? 0 : h1.data;
int d2 = h2 == null ? 0 : h2.data;
int sum = d1 + d2 + carry;
int nextDigit = sum%10;
carry = sum/10;
// add node
Node newNode = new Node(nextDigit);
newNode.next = list;
list = newNode;
if(h1 != null) h1 = h1.next;
if(h2 != null) h2 = h2.next;
}
// restore original lists
num1 = reverseLinkedList(num1);
num2 = reverseLinkedList(num2);
return list;
}
static Node reverseLinkedList(Node head){
Node h1 = head;
Node h2 = null;
while(h1 != null){
Node t = h1;
h1 = h1.next;
t.next = h2;
h2 = t;
}
return h2;
}
}