Back to home
Logicmojo - Updated March 28, 2022

Two non-empty linked lists representing two non-negative integers are given to you. The digits are kept in reverse order, with a single digit in each of their nodes. Return the sum as a linked list after adding the two numbers.

Input 1 :
firstList = [3,1,2]
secondList = [4,7,6]
Output 1 : [7,8,8]
Explanation : 312 + 476 = 788.

Input 2 :
firstList = [7,5,9,4,6]
secondList = [8,4]
Output 2: [5,0,0,5,6]

Explanation 2:
The resultant linked-list is 5 -> 0 -> 0 -> 5 -> 6. Adding the linked lists in the above manner with the laws of sum and carry of addition gives us 5 -> 0 -> 0 -> 5 -> 6.

Approach

This is how we address the challenge. We'll traverse both lists and append zeros to the list with the less digits until both integers have the same number of digits. Then we may recursively begin at the beginning nodes of both lists, and the function will go forward on both lists until we reach the end. We'll keep generating new nodes to store the sum of the digits as we recurse, and the recursive function will return the carry to the next node for the sum operation.

Algorithm

1. Perform a traverse on both linked lists and append zeros to the end of the shorter list to make it the same length as the large list.

2. Start a recursive function from the start nodes of both the lists, where the function will further call the next nodes of the list.

3. The recursion continues till we reach the end of a linked list.

4. We'll keep adding new nodes to record the sum of digits of our result as we continue our recursion, and the recursive function will return the carry to the next step in each recursive call.

C++ Implementation:

```// 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) {
}
Node * rest = reverse(head -> next);
return rest;
}

Node * solve(Node * list1, Node * list2) {
list1 = reverse(list1);
list2 = reverse(list2);
}
```

Java Implementation:

```/*
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;
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) {
return result;
}
```

Python Implementation:

```# class Node:

#     def __init__(self, data):
#         self.data = data
#         self.next = None
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)
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)
```

Time Complexity: O(n + m),
where, 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.