Problem Statement
Given 2 numbers, where each digit is represented by nodes of a LinkedList, find the sum of the 2 numbers represented as LinkedList.
Sample Test Cases
- Input 1:
- firstList = 7 5 9 4 6
- secondList = 8 4
- Output 1:
- Result = 5 0 0 5 6
Explanation 1:
Adding the linked lists in the above manner with the rules of sum and carry of addition, we get the resultant linked-list as 5 -> 0 -> 0 -> 5 -> 6.
- Input 2:
- firstList = 0
- secondList = 0
- Output 2:
- Result = 0
Explanation 2:
Both the linked lists in the above example represent the number 0, so the result is also a single node with the value 0.
Approach
We approach this problem as follows. We will perform a traversal on both lists and append zeros on the list which has a lesser number of digits till both numbers have an equal number of digits. Then we can recursively start from the start nodes of both lists, where the function recursively moves ahead on both lists till we reach the end. In the process of recursion, we will keep creating new nodes which will store the sum of the digits, and the recursive function returns the carry onto the next node for the sum operation.
The algorithm is as described below:
- Perform a traversal on both the linked lists and make the shorter list of length equal to the long list by appending zeros to its end.
- Start a recursive function from the start nodes of both lists, where the function will further call the next nodes of the list.
- The recursion continues till we reach the end of a linked list.
- While continuing our recursion, we will keep adding new nodes which will store the sum of digits of our result, and the recursive function will return the carry to the next step in each recursive call.
Add Two Numbers: Solve Problem
C++ Code
// class Node {
// public:
// int data;
// Node* next;
// };
Node * addTwoLists(Node * first, Node * second) {
Node * res = NULL;
Node * temp;
Node * prev = NULL;
int carry = 0, sum = 0;
while (first != NULL || second != NULL) {
sum = carry;
sum += first != NULL ? first -> data : 0;
sum += second != NULL ? second -> data : 0;
if (sum >= 10) {
carry = 1;
} else {
carry = 0;
}
sum %= 10;
temp = newNode(sum);
if (res != NULL) {
prev -> next = temp;
} else {
res = temp;
}
prev = temp;
if (first) {
first = first -> next;
}
if (second) {
second = second -> next;
}
}
if (carry > 0)
temp -> next = newNode(carry);
return res;
}
Node * reverse(Node * head) {
if (head == NULL || head -> next == NULL) {
return head;
}
Node * rest = reverse(head -> next);
head -> next -> next = head;
head -> next = NULL;
return rest;
}
Node * solve(Node * list1, Node * list2) {
list1 = reverse(list1);
list2 = reverse(list2);
Node * added = addTwoLists(list1, list2);
return added;
}
Java Code
/*
static class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
*/
public static Node addTwoLists(Node first, Node second) {
Node start1 = new Node(0);
start1.next = first;
Node start2 = new Node(0);
start2.next = second;
addPrecedingZeros(start1, start2);
Node result = new Node(0);
if (sumTwoNodes(start1.next, start2.next, result) == 1) {
Node dummy = new Node(1);
dummy.next = result.next;
result.next = dummy;
}
return result.next;
}
public static int sumTwoNodes(Node first, Node second, Node result) {
if (first == null) {
return 0;
}
int sum = 0;
sum += first.data;
sum += second.data;
sum += sumTwoNodes(first.next, second.next, result);
Node dummy = new Node(sum % 10);
dummy.next = result.next;
result.next = dummy;
return sum / 10;
}
public static void addPrecedingZeros(Node start1, Node start2) {
Node next1 = start1.next;
Node next2 = start2.next;
while (next1 != null && next2 != null) {
next1 = next1.next;
next2 = next2.next;
}
if (next1 == null) {
if (next2 != null) {
while (next2 != null) {
Node dummy = new Node(0);
dummy.next = start1.next;
start1.nedummy dummy;
next2 = next2.next;
}
}
} else if (next2 == null) {
if (next1 != null) {
while (next1 != null) {
Node dummy = new Node(0);
dummy.next = start2.next;
start2.next = dummy;
next1 = next1.next;
}
}
}
}
public static Node solve(Node first, Node second) {
Node result = addTwoLists(first, second);
return result;
}
Python Code
# class Node:
# def __init__(self, data):
# self.data = data
# self.next = None
def addTwoLists(self, first, second):
prev = None
temp = None
carry = 0
while first is not None or second is not None:
if first is None:
firstData = 0
else:
firstData = first.data
if second is None:
secondData = 0
else:
secondData = second.data
Sum = carry
Sum += firstData
Sum += secondData
if Sum >= 10:
carry = 1
else:
carry = 0
Sum %= 10
temp = Node(Sum)
if self.head is None:
self.head = temp
else:
prev.next = temp
prev = temp
if first is not None:
first = first.next
if second is not None:
second = second.next
if carry > 0:
temp.next = Node(carry)
Complexity Analysis
- Time Complexity: O(n + m) // n = length of 1st list, m = length of 2nd list.
- Space Complexity: O(n + m) // Temporary linked list needed to store results in form of dummy node.
FAQs
Q. Why are zeros appended to the end of the smaller linked list?
Ans. Zeroes are appended to the end of the linked list which is equivalent to adding zeros before a number, the value the list represents doesn’t change, but the implementation becomes easier for the problem logic.
Q. How is the carry calculated for the sum of digits?
Ans. The carry is calculated for the sum of digits as “If the sum of digits exceeds 10, the carry is 1, else it is 0.”
