Add Two Linked Lists

1. You are given a partially written LinkedList class.
2. You are required to complete the body of addLinkedLists function. The function is passed two linked lists which represent two numbers - the first element is the most significant digit and the last element is the least significant digit. The function is expected to add the two linked list and return a new linked list.

The following approaches are not allowed :
    1. Don't reverse the linked lists in order to access them from least significant digit 
     to most significant.
     2. Don't use arrays or explicit extra memory.
     3. Don't convert linked lists to number, add them up and convert the result back 
     to a linked list.

Hint - You are expected to take help of recursion to access digits from least significant to most significant. You have to tackle the challenge of unequal size of lists and manage carry where required.

3. Input and Output is managed for you. 

Note-> Make sure to set head and tail appropriately because addFirst and addLast has been used to test their values in the input-output code.

Input Format

Input is managed for you

Output Format

Output is managed for you

Question Video Constraints

1. Time complexity -> O(n)
2. Space complexity -> Recursion space, O(n)

Sample Input

1
1
3
9 9 9
10
20

Sample Output

1 
9 9 9 
1 0 0 0 
10 1 0 0 0 20 

• Editorial

  The problem here deals with adding two linked list wherein we are not allowed the following operations:

  1. We are not allowed convert the list to integers

  2. We are not allowed to convert the list to arrays

  3. We are not allowed to reverse the list

  To solve this problem we will use a recursive approach. The idea here is that we need to add the list but as we know that addition is only possible when traversing from the end like adding firstly the unit place elements and then carry forwarding to the next place and so on. This generalized process here we will try to implement using recursion as we are not allowed to reverse the list.

  Here we will be passing the current element and its place as parameters to the recursive function and we will make recursive calls till we hit the base case. Our recursive function is built to return the carry forward number if any. So for the base case when we have no elements after the unit place (which is true) then we return 0. Now for the unit place, we have supposed both the numbers so we add the unit places with the carry number and then add the resultant number at the head of the global resultant linked list. Adding it to the head always ensure that firstly unit place is placed at head later on the tenth place is added and then hundredth place and so on this makes our resultant list to be in order and hence no need to reverse the obtained result.

  To summarize we are traversing over the lists until we hit the base case, thereafter when we are popping out from the recursive stack we are entering the result at its correct place and returning the carry value. Also, we are keeping a track of lists with different digits to avoid miscalculation, as in that case when one element is not long enough to avoid error we are not considering it (this explains the if conditions in the code).

  

  Below is the implementation in Java:

  public static LinkedList addTwoLists(LinkedList one, LinkedList two) {
                                      LinkedList res = new LinkedList();
                                       int carry = addTwoLists(one.head, two.head, one.size, two.size, res);
                                      if(carry > 0){
                                      res.addFirst(carry);
                                      } 
                                      return res;
                                  }
                                  public static int addTwoLists(Node on, Node tn, int pio, int pit, LinkedList res){
                                      if(on == null && tn == null){
                                      return 0;
                                      } 
                                      int carry = 0;
                                      int data = 0;
                                      if(pio > pit){
                                      carry = addTwoLists(on.next, tn, pio - 1, pit, res);
                                      data = carry + on.data;
                                      } else if(pio < pit){
                                      carry = addTwoLists(on, tn.next, pio, pit - 1, res);
                                      data = carry + tn.data;
                                      } else {
                                      carry = addTwoLists(on.next, tn.next, pio - 1, pit - 1, res);
                                      data = carry + on.data + tn.data;
                                      } 
                                      carry = data / 10;
                                      data = data % 10;
                                       res.addFirst(data);
                                      return carry;
                                  }

  java false

  Time Complexity: O(max(n,m))

  The time complexity for the function is linear as we are recursively calling the function for the length of the longer list.

  Space Complexity: O(max(n,m))

  The space complexity for the function is linear we are recursively calling the function for the length of the longer list along with the additional space used for storing the resultant list.

• Asked in Companies
• Related Topics