Adding Two Numbers using Linked List

In this blog, we will see adding two numbers using a LinkedList with the time complexity of O(n).

Represent both the numbers using Linked List in the reverse order.
For example, if we want to add two numbers

1234 +46 = 1280

LinkedList 1 would represent the values in the form of 4->3->2->1
LinkedList 2 would represent the values in the form of 6 -> 4

The resultantList will have the value as 1->2->8->0
  

The below code would iterate both the linkedlist as the same time.
Here is the algorithm.

1. Get the reference of both the LinkedList's head node and declare a flag to Identify whether the sum has 2 digits.
Iterate until node1.getData is not null or  node2.getData is not null

2. Get the values associated to the node and store it in a different variables.

3. Add both the values
4. For the first iteration, carried flag will be false.
       From second iteration onwards, this flag might be true depending upon the carried number, If we add 8 + 4, the carried number will be 1 here.
      If we have carried number then
           a. Get the head node value
           b. add it to the sum.
           c. remove the head node.
           d. Mark the carried flag as false.

5. If the number of digits is 2
    a)      then split the digits as ones and tens.
        For example if the sum is 12
          ones -> 2
          tens -> 1
        
        Add ones and tens to the resultant List
Such that the resultantList head always holds the value of the carried over number, In this case the head will have the value as 1, the subsequent node will have the value as 2.

    b.  If the sum value is single digit then
         Add the value to the resultant Linked List.

6. Traverse to the next node from List1 and List2, so that node1 -> node1.next, node2 -> node.next
7. Repeat the steps until both the list are completely traversed.
             

The below java code, iterates all the nodes in the list only one time, so we get the O(n) complexity.
The code inside the while loop are all constant time operations.

public static LinkedList add(LinkedList list1, LinkedList list2) {

        Node node1 = list1.head;

        Node node2 = list2.head;

        LinkedList returnList = new LinkedList();

        boolean isCarried = false;

        while((node1 != null && node1.getData() !=null) || (node2 !=null && node2.getData() != null)) {

            int k=0;

            int l=0;

            if(node1 != null && node1.getData() !=null) {

                k = Integer.valueOf(node1.getData());

            }

            if(node2 != null && node2.getData() !=null) {

                l = Integer.valueOf(node2.getData());

            }

            int m = k + l;

            if(isCarried) {

                isCarried = false;

                m += Integer.valueOf(returnList.head.getData());

                returnList.remove(0);

            }

            String value = String.valueOf(m);

            if(value.length()==2) {

                returnList.add(0, value.substring(1));

                returnList.add(0, value.substring(0,1));

                isCarried = true;

            } else {

                returnList.add(0, value);

            }

            if(node1 != null) {

                node1 = node1.getNext();

            }

            if(node2 != null) {

                node2 = node2.getNext();

            }

        }

        return returnList;

    }