Linked List : Add two numbers represented by linked lists

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:

add two numbers represented in linked list


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.

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 add two numbers using linked list is O(N).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s