1.
Introduction
2.
Problem Statement
3.
Driver code
3.1.
Class ListNode
3.2.
Function printList()
4.
4.1.
Code
4.2.
java
4.2.1.
Output
4.2.2.
Complexity Analysis
5.
5.1.
Code
5.2.
java
5.2.1.
Output
5.2.2.
Complexity Analysis
6.
6.1.
Code
6.2.
java
6.2.1.
Output
6.2.2.
Complexity Analysis
7.
7.1.
Code
7.2.
java
7.2.1.
Output
7.2.2.
Complexity Analysis
8.
8.1.
8.2.
What are the various ways to add two numbers represented by a linked list?
8.3.
8.4.
Explain the concept of recursion?
9.
Conclusion
Last Updated: Mar 27, 2024
Medium

Ravi Khorwal
0 upvote

## Introduction

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

Related Article: How To Master Linked List And Its Importance

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.

• java

### java

``public class Main { private static ListNode reverseLinkedList(ListNode head) {    ListNode previous = null, current = head, next = null;    while (current != null) {      next = current.next;      current.next = previous;      previous = current;      current = next;    }    head = previous;    return head;  } // function to add two numbers  private static ListNode addTwoNumbers(ListNode headList1, ListNode headList2) {    if (headList1 == null)      return headList2;    if (headList2 == null)      return headList1;    ListNode result = null, head = null;    int carry = 0;        // reverse both the linked lists    headList1 = reverseLinkedList(headList1);    headList2 = reverseLinkedList(headList2);    // while end of list is not reached    while (headList1 != null || headList2 != null) {      int sum = 0;      // add value in linkedlist 1      if (headList1 != null) {        sum += headList1.val;        headList1 = headList1.next;      }      // add value in linkedlist 2      if (headList2 != null) {        sum += headList2.val;        headList2 = headList2.next;      }      // add carry      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);    }    head = reverseLinkedList(head);    return head;  }}``

#### 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.

• java

### java

``import java.util.Stack;public class Main {  static ListNode head;  static ListNode tail;  // function to add node to the linked list  private static void appendNode(int value) {    // add first node    if (head == null) {      head = new ListNode(value);      tail = head;      return;    }    // add node    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    if (head != null) {      head = null;    }    // add node to linked list till the stack is empty    while (!s.isEmpty()) {      appendNode(s.pop());    }    return head;  }  // function to add two numbers  private static ListNode addTwoNumbers(ListNode headList1, ListNode headList2) {    // if first linked list is empty then return the second linked list   if (headList1 == null)     return headList2;// if first linked list is empty then return the second linked list   if (headList2 == null)     return headList1;        Stack<Integer> stack1 = new Stack<Integer>();    Stack<Integer> stack2 = new Stack<Integer>();    Stack<Integer> stackResult = new Stack<Integer>();    // push headList1 into the first stack    ListNode temp = headList1;    while (temp != null) {      stack1.push(temp.val);      temp = temp.next;    }    // push headList2 into the second stack    temp = headList2;    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    return createLinkedList(stackResult);  }}``

#### 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 backtracking and recursion 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.

• java

### java

``public class Main {  private static ListNode addition(ListNode headList1, ListNode headList2, int size1, int size2) {    ListNode node = new ListNode(0);    // base case    if (headList1.next == null && headList2.next == null) {      // add last nodes of both the linked list      node.val = (headList1.val + headList2.val);      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      returnedNode = addition(headList1.next, headList2.next, size1 - 1, size2 - 1);      // add current nodes and append the carry      node.val = (headList1.val + headList2.val) + ((returnedNode.val) / 10);    }    // or else move in big linked list    else {      // recursively call the function and move ahead in the bigger linked list      returnedNode = addition(headList1, headList2.next, size1, size2 - 1);      // 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  private static ListNode addTwoNumbers(ListNode headList1, ListNode headList2) {    // if first linked list is empty then return the second linked list   if (headList1 == null)     return headList2;    // if first linked list is empty then return the second linked list   if (headList2 == null)     return headList1;    ListNode temp1, temp2, result = new ListNode(0), returnedNode;    temp1 = headList1;    temp2 = headList2;    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) {      returnedNode = addition(headList1, headList2, size1, size2);    } else {      returnedNode = addition(headList2, headList1, size2, size1);    }    // 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.

• java

### java

``public class Main {  static ListNode headList1, headList2, result, current;  static int carry;  // function to add node to the linked list  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    if (headList1 != current) {      propogatecarry(headList1.next);      int sum = carry + headList1.val;      carry = sum / 10;      sum %= 10;      // add sum to result      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    addSameSize(list1.next, list2.next);    // add the digits of current nodes and propagated carry    int sum = list1.val + list2.val + carry;    carry = sum / 10;    sum = sum % 10;    // add sum to result    appendNode(sum);  }  // function to add two numbers  private static ListNode addTwoNumbers(ListNode list1, ListNode list2) {    headList1 = list1;    headList2 = list2;    // if first linked list is empty return second linked list    if (headList1 == null) {      result = headList2;      return result;    }    // if second linked list is empty return first linked list    if (headList2 == null) {      result = headList1;      return result;    }    ListNode temp1 = headList1;    ListNode temp2 = headList2;    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) {      addSameSize(headList1, headList2);    } else {      // swap linked list if second linked list is larger than first      if (size1 < size2) {        ListNode temp = headList1;        headList1 = headList2;        headList2 = temp;      }            int difference = Math.abs(size1 - size2);      // traverse the difference in the first linked list      ListNode temp = headList1;      while (difference-- >= 0) {        current = temp;        temp = temp.next;      }      // add linked list with same size      addSameSize(current, headList2);      // add the remaining numbers in the first number and carry      propogatecarry(headList1);    }        // add carry to the linked list    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)

Related Articles: -

### What is a linked list?

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.

To add two numbers represent adding teh digits of the two inked list by traversing both lists simultaneously and then adding corresponding digits along with any carry from the previous sum. Continue until both lists are exhausted, creating a new linked list for the result.

### 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.

## Conclusion

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.

Also read palindrome number in python.

Now that you know how to approach a problem in Linked List try out some questions based on them on our Coding Ninjas Studio Platform! To study more about Linked Lists, refer to Applications Of Linked Lists

Check out our Interview guide for Product Based CompaniesData Structures and Algorithms-guided path to learn Data Structures and Algorithms from scratch as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, UberMicrosoft, etc. on Coding Ninjas Studio.

Live masterclass