 ## Introduction

Linked lists are one of the frequently asked data structures in interviews. Some of the questions on the linked list asked in product-based companies like Amazon, Microsoft are  Detect And Remove Cycle, Merge two sorted linked lists, etc.

This blog will discuss the interview problem: add two numbers represented by a linked list previously asked in companies like Amazon, Flipkart, Microsoft, Morgan Stanley, etc. This blog requires a thorough understanding of Linked List so, please go through the blog A Brief Introduction To Linked Lists for a better understanding.

## Problem Statement

Two numbers are represented by two linked lists. Write a program that adds both numbers.

For example:-

Input:

linkedList1: 1 -> 2 -> 3 // represents number 123

linkedList2: 9 -> 8 -> 7 // represents number 987

Output:

resultantLinkedList: 1 -> 1  -> 1 -> 0 // represents number 1110

Explanation:

123 + 987 = 1110

Now let’s see various approaches to add two numbers represented by a linked list.

## Driver code

Let’s check out the main function before moving to each approach. We initialize three linked lists in the main function: first linked list, second linked list, and the resultant linked list.

Main function:

```public class Main {
public static void main(String[] args) {
ListNode list1 = new ListNode(1);
list1.next = new ListNode(2);
list1.next.next = new ListNode(3);
printList(list1);

ListNode list2 = new ListNode(9);
list2.next = new ListNode(8);
list2.next.next = new ListNode(7);
printList(list2);

printList(result);
}
}
```

Let’s also check out the ListNode class and printList() function, repeatedly used in the program.

Class ListNode:

```// class representing the node in the linked
class ListNode {
int val;
ListNode next;

ListNode(int val) {
this.val = val;
}
}
```

Function printList():

```// function to print linked list
private static void printList(ListNode head) {
}
System.out.println();
}
```

In this approach, we reverse the linked lists as the numbers have to be added from the right end. Then traverse through the linked list and add the values one by one from the node. If the sum exceeds 9, the resultant linked list is appended accordingly with the carry and remainder. The result obtained in this approach is reversed, so the linked list must be reversed to get the final result.

Steps:

1. Check if any one of the linked lists is empty; return the other linked list.
2. Reverse both the linked lists.
4. Add the digits each from respective linked lists and traverse to the next node.
5. If one of the linked lists has reached the end, then take the remaining digits as 0.
6. Continue the above process till the end is reached for both the linked lists.
7. If the sum of two digits exceeds 9, the resultant linked list is appended accordingly with the carry and remainder.

Code:

```public class Main {
ListNode previous = null, current = head, next = null;

while (current != null) {
next = current.next;
current.next = previous;
previous = current;
current = next;
}
}
// function to add two numbers

ListNode result = null, head = null;
int carry = 0;

// reverse both the linked lists

// while end of list is not reached
int sum = 0;
}
}
sum += carry;

int value = sum % 10;
carry = sum / 10;
// node with the remainder value
ListNode node = new ListNode(value);
if (result != null) {
result.next = node;
result = result.next;
} else {
result = head = node; // for the first iteration
}
}
// if carry is present
if (carry > 0) {
result.next = new ListNode(carry);
}

}
}
```

Output:

```First Linked List is 1 2 3
Second Linked List is 9 8 7
Resultant Linked List is 1 1 1 0
```

Complexity Analysis:

• Time Complexity: O(m + n) as the linked lists are traversed once.
• Space Complexity: O(m + n)  as extra space is required to store the output numbers.

m: number of nodes in the first linked list

n: number of nodes in the second linked list

In this approach, the nodes are passed into stacks. The values are added from the top to the resultant stack. The result obtained in this approach is converted back to a linked list.

Steps:

1. Check if any one of the linked lists is empty; return the other linked list.
2. Create three stacks: stack1, stack2, stackResult.
3. Fill stack1 with node values from the first linked list.
4. Fill stack2 with node values from the second linked list.
5. Fill stack3 by creating new nodes and setting the new node’s value to the sum of the top values of stack1 and stack3 and carry until list1 and list2 are empty.
6. If carry is remaining, then push it into stack3.
7. Convert the stack to a linked list and return the linked list.

Code:

```import java.util.Stack;

public class Main {
static ListNode tail;

private static void appendNode(int value) {
return;
}

ListNode node = new ListNode(value);
tail.next = node;
tail = node;
}

// function to create a linked list from stack
private static ListNode createLinkedList(Stack<Integer> s) {
// initialize head as null if the head is pointing to some existing list
}

while (!s.isEmpty()) {
appendNode(s.pop());
}
}

// function to add two numbers
// if first linked list is empty then return the second linked list
// if first linked list is empty then return the second linked list

Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
Stack<Integer> stackResult = new Stack<Integer>();

// push headList1 into the first stack
while (temp != null) {
stack1.push(temp.val);
temp = temp.next;
}

// push headList2 into the second stack
while (temp != null) {
stack2.push(temp.val);
temp = temp.next;
}

int sum = 0, carry = 0, value1, value2;

// add the popped digits till one of the stacks becomes empty
while ((!stack1.empty()) && (!stack2.empty())) {
value1 = stack1.pop();
value2 = stack2.pop();

sum = (value1 + value2 + carry) % 10;
carry = (value1 + value2 + carry) / 10;

// store sum in the resultant stack
stackResult.push(sum);
}

// if stack1 still has some digits left, add those digits to the sum
while (!stack1.isEmpty()) {
value1 = stack1.pop();

sum = (value1 + carry) % 10;
carry = (value1 + carry) / 10;

stackResult.push(sum);
}

// if stack2 still has some digits left, add those digits to the sum
while (!stack2.isEmpty()) {
value2 = stack2.pop();

sum = (value2 + carry) % 10;
carry = (value2 + carry) / 10;

stackResult.push(sum);
}

// add remaining carry to the sum
if (carry > 0) {
stackResult.push(carry);
}

// return the resultant stack as a linked list
}
}
```

Output:

```First Linked List is 1 2 3
Second Linked List is 9 8 7
Resultant Linked List is 1 1 1 0
```

Complexity Analysis:

• Time Complexity: O(m + n)
• Space Complexity: O(m + n) as extra space is required for stacks.

In this approach, the concept of recursion and backtracking is used. After the complete traversal of the linked list, the node values are added through backtracking.

Steps:

1. Check if any one of the linked lists is empty; return the other linked list.
2. Calculate the sizes of both the linked lists.
3. Initialize returnedNode to store the previously added value.
4. Compare the size of the linked list and pass the linked list with the smaller size first with the respective size to the addition(). The result is stored in returnedNode.
5. In addition() if both are of equal size, then a recursive call is made, and both the linked list traverses one node.
6. In addition() if both are not of equal size, then a recursive call is made, and the bigger linked list traverses one node.
7. Now traverse both linked lists till the end, i.e., till the base condition is reached.
8. Through backtracking, addition operations are now performed.
9. returnedNode stores the rightmost digit of the latest previous value.
10. The node with the current value is returned to obtain the output.

Code:

```public class Main {
ListNode node = new ListNode(0);

// base case
node.next = null;
return node;
}

// a node that contains the sum of previously added number
ListNode returnedNode;

//i f sizes of both the linked list are the same then move in both linked list
if (size2 == size1) {
// recursively call the function and move ahead in both linked list

// add current nodes and append the carry
}
// or else move in big linked list
else {
// recursively call the function and move ahead in the bigger linked list

// add the current node value of bigger linked list and append the carry
node.val = (headList2.val) + ((returnedNode.val) / 10);
}

// set returned node with the right most digit
returnedNode.val = (returnedNode.val) % 10;

// set the returned node to the current node
node.next = returnedNode;

return node;
}

// function to add two numbers
// if first linked list is empty then return the second linked list

// if first linked list is empty then return the second linked list

ListNode temp1, temp2, result = new ListNode(0), returnedNode;

int size1 = 0, size2 = 0;

// find the size of first linked list
while (temp1 != null) {
temp1 = temp1.next;
size1++;
}

// find the size of second linked list
while (temp2 != null) {
temp2 = temp2.next;
size2++;
}

// compare the size of linked list and pass the linked list with the smaller size first with the respective size
if (size2 > size1) {
} else {
}

// if the value of returned node is greater than 9 split the digits
if (returnedNode.val >= 10) {
result.val = (returnedNode.val) / 10;
returnedNode.val = returnedNode.val % 10;
result.next = returnedNode;
} else
result = returnedNode;

return result;
}
}
```

Output:

```First Linked List is 1 2 3
Second Linked List is 9 8 7
Resultant Linked List is 1 1 1 0
```

Complexity Analysis:

• Time Complexity: O(m + n)
• Space Complexity: O(m + n)

In this approach, first, the larger linked list is taken and traversed until both the linked lists have equal sizes. When this condition is hit, the digits and carry are added. After this, the remaining digits in the larger linked list are added to obtain the final result.

Steps:

1. Check if any one of the linked lists is empty; return the other linked list.
2. Calculate the sizes of both the linked lists.
3.  If sizes are the same, then calculate the sum using the recursion function add addSameSize.
4. If the size is not the same, swap the linked list such that the second list is larger than the first.
5. Traverse the number of nodes equal to the difference in sizes in the larger linked list.
6. Now when they are of the same size and can be added together.
7. After this, add the remaining digits of the bigger linked list along with the carry.
8. If carry is left, append a node to the result.

Code:

```public class Main {
static int carry;

private static void appendNode(int val) {
ListNode newNode = new ListNode(val);
newNode.next = result;
result = newNode;
}

private static void propogatecarry(ListNode list) {
// if the difference in the number of nodes are not traversed then add carry
int sum = carry + headList1.val;
carry = sum / 10;
sum %= 10;

appendNode(sum);
}
}

private static void addSameSize(ListNode list1, ListNode list2) {
// check if the list1 is null
// if list1 is null then list2 is also null as they are of same size
if (list1 == null)
return;

// recursively add the remaining nodes and get the carry

// add the digits of current nodes and propagated carry
int sum = list1.val + list2.val + carry;
carry = sum / 10;
sum = sum % 10;

appendNode(sum);
}

// function to add two numbers
private static ListNode addTwoNumbers(ListNode list1, ListNode list2) {

return result;
}

return result;
}

int size1 = 0, size2 = 0;

// find the size of first linked list
while (temp1 != null) {
temp1 = temp1.next;
size1++;
}

// find the size of second linked list
while (temp2 != null) {
temp2 = temp2.next;
size2++;
}

// if linked list of same size
if (size1 == size2) {
} else {
// swap linked list if second linked list is larger than first
if (size1 < size2) {
}

int difference = Math.abs(size1 - size2);

// traverse the difference in the first linked list
while (difference-- >= 0) {
current = temp;
temp = temp.next;
}

// add the remaining numbers in the first number and carry
}

if (carry > 0) {
appendNode(carry);
}
return result;
}
}
```

Output:

```First Linked List is 1 2 3
Second Linked List is 9 8 7
Resultant Linked List is 1 1 1 0
```

Complexity Analysis:

• Time Complexity: O(m + n)
• Space Complexity: O(m + n)

A Linked List is a linear data structure where the elements called nodes are stored at non-contiguous memory locations.

What are the various ways to add two numbers represented by a linked list?

The various methods to add two numbers represented by a linked list are backtracking, stacks, normal traversal, etc.

What is a stack?

Stacks are linear data structures that allow us to store and retrieve data sequentially. It follows the LIFO, i.e., Last In First Out, for the insertion and abstraction of data.

Explain the concept of recursion?

Recursion is a method of solving a problem that depends on solutions to smaller instances of the same problem. In this, the function calls itself till the base condition is reached.

## Key Takeaways

This blog covered the various methods to add two numbers represented by a linked list. The methods discussed are the traversal approach, recursive approach, backtracking approach, and an approach using stacks.

Now that you know how to approach a problem in Linked List try out some questions based on them on our CodeStudio Platform!

Don’t stop here. Check out our Data Structures and Algorithms-guided path to learn Data Structures and Algorithms from scratch. We hope you found this blog useful. Feel free to comment down below if you have a better insight into the above approach.

By: Hari Sapna Nair