Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
2.
Problem Statement
3.
Driver code
3.1.
Class ListNode
3.2.
Function printList()
4.
Add two numbers represented by a linked list: Traversal Approach
4.1.
Code
4.2.
java
4.2.1.
Output
4.2.2.
Complexity Analysis 
5.
Add two numbers represented by a linked list: Using Stack
5.1.
Code
5.2.
java
5.2.1.
Output
5.2.2.
Complexity Analysis
6.
Add two numbers represented by a linked list: Using Backtracking
6.1.
Code
6.2.
java
6.2.1.
Output 
6.2.2.
Complexity Analysis 
7.
Add two numbers represented by a linked list: Recursive approach
7.1.
Code
7.2.
java
7.2.1.
Output 
7.2.2.
Complexity Analysis
8.
Frequently Asked Questions
8.1.
What is a linked list?
8.2.
What are the various ways to add two numbers represented by a linked list?
8.3.
What is add two numbers represented by linked lists?
8.4.
Explain the concept of recursion?
9.
Conclusion
Last Updated: Mar 27, 2024
Medium

Add Two Numbers Represented by a Linked List

Author Ravi Khorwal
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

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. 

add two numbers represented by linked lists

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. 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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) {
    // linked list 1
    ListNode list1 = new ListNode(1);
    list1.next = new ListNode(2);
    list1.next.next = new ListNode(3);
    System.out.print("First Linked List is ");
    printList(list1);

    // linked list 2
    ListNode list2 = new ListNode(9);
    list2.next = new ListNode(8);
    list2.next.next = new ListNode(7);
    System.out.print("Second Linked List is ");
    printList(list2);

    // resultant linked list
    ListNode result = addTwoNumbers(list1, list2);
    System.out.print("Resultant Linked List is ");
    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) {
    while (head != null) {
      System.out.print(head.val + " ");
      head = head.next;
    }
    System.out.println();
}

Add two numbers represented by a linked list: Traversal Approach

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.
  3. Traverse 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.
  8. Return the head of the resultant linked list after reversing.

Code

  • 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

Add two numbers represented by a linked list: Using Stack

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

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

Add two numbers represented by a linked list: Using Backtracking

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.

Code

  • 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)  

Add two numbers represented by a linked list: Recursive approach

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

  • 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: - 

Add two numbers represented by the linked lists | Part-1

Add two numbers represented by the linked lists | Part-2

Add two numbers represented by the linked lists | Part-3

Frequently Asked Questions

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.

What is add two numbers represented by linked lists?

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.

Previous article
How to Find all the Palindromic Partitions of a String
Next article
Difference between Iteration and Recursion
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass