Given two linked list, each node contains one digit number, we need to add these two linked list. Result should be stored in third linked list.
It should be noted that the head node contains the most significant digit of the number.

For example, two numbers 12345 and 56789 are represented in form of linked list as follows:

### Analysis

Since addition starts from the least significant digit, we first need to visit the last node of both the lists and add them up, create new node to store the result, take care of the carry if any and the link the result node to node which will be added to second least significant node and continue.
So we have to go to the end of lists and move back one node at at a time. This is very good case for recursion. However, we need to take into account the difference in number of digits in two number.

So before starting recursion, we need to do some calculation and move the longer list pointer to appropriate place so that we need the last node of both lists at same time.

Other thing is we need to take care of is carry. If two digits add more than 10, we need to forward the carry to next node and add it to them. If most significant digit addition results in carry, we need to create an extra node to store carry.

Third thing we need see is that we link the resulting nodes correctly, so that final list in correct order.

There is no algorithms as such, this problem involves working with recursion on linked lists and pointer handling.So let’s see the code.

### Test cases

1. Two lists are of same length
L1 = 1->2->3->NULL
L2 = 4->5->6->NULL

2. Two lists of different length
L1 = 1->2->3->4->NULL
L2 = 4->5->6->NULL

3. One list being NULL
L1= NULL
L2 = 4->5->6->NULL

4. Both lists are NULL
L1 = NULL
L2 = NULL

5. Carry generated
L1 = 9->4->5->NULL
L2 = 2->4->6->NULL

Since we need to traverse the no of nodes in longer list, complexity of algorithm would be O(N), where N is no of nodes in longer list. Also we need N extra nodes to store the result. Hence space complexity of algorithm to add two numbers using linked list is O(N).