Linked list basics can be read at this post.

# Add two numbers represented by linked lists

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:

Resulting linked list is liked

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

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.

## Code to add two numbers represented in linked list

### 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

**is O(N).**__add two numbers using linked list__