Add Two Numbers Represented by a Linked List

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

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) {
    // 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:

Check if any one of the linked lists is empty; return the other linked list.
Reverse both the linked lists.
Traverse the linked lists.
Add the digits each from respective linked lists and traverse to the next node.
If one of the linked lists has reached the end, then take the remaining digits as 0.
Continue the above process till the end is reached for both the linked lists.
If the sum of two digits exceeds 9, the resultant linked list is appended accordingly with the carry and remainder.
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:

Check if any one of the linked lists is empty; return the other linked list.
Create three stacks: stack1, stack2, stackResult.
Fill stack1 with node values from the first linked list.
Fill stack2 with node values from the second linked list.
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.
If carry is remaining, then push it into stack3.
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:

Check if any one of the linked lists is empty; return the other linked list.
Calculate the sizes of both the linked lists.
Initialize returnedNode to store the previously added value.
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.
In addition() if both are of equal size, then a recursive call is made, and both the linked list traverses one node.
In addition() if both are not of equal size, then a recursive call is made, and the bigger linked list traverses one node.
Now traverse both linked lists till the end, i.e., till the base condition is reached.
Through backtracking, addition operations are now performed.
returnedNode stores the rightmost digit of the latest previous value.
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:

Check if any one of the linked lists is empty; return the other linked list.
Calculate the sizes of both the linked lists.
If sizes are the same, then calculate the sum using the Recursion function add addSameSize.
If the size is not the same, swap the linked list such that the second list is larger than the first.
Traverse the number of nodes equal to the difference in sizes in the larger linked list.
Now when they are of the same size and can be added together.
After this, add the remaining digits of the bigger linked list along with the carry.
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)

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.