# Add a single-digit number to a linked list representing a number

Given a singly linked list whose nodes represents digits of a number, add a single-digit number to it.

For example, consider the linked list 9 -> 9 -> 9 -> 3 -> NULL which represents the number 9993. Adding a single-digit number 7 to it should result in the linked list 1 -> 0 -> 0 -> 0 -> 0 -> NULL which corresponds to number 10000.

The idea is to solve this problem using the basic algorithm for addition of two numbers. But since the given list is a singly linked list, we can’t iterate it in backward direction. Therefore, in order to facilitate the addition, we can reverse the given list.

In the reversed list, we start by adding the given single-digit number to the digit at the first node. If the resultant sum is two-digit number, we update the node with single-digit sum and move the carry to the next node. This process is repeated while there is a carry. If we reach the last node and a carry exists, we add a new node at the end of linked list with carry as the value. Finally, reverse the list again to restore the original order.

Output:

Original Linked List: 9 -> 9 -> 9 -> 9 -> 3 -> NULL
Resultant Linked List: 1 -> 0 -> 0 -> 0 -> 0 -> 0 -> NULL

The time complexity of above solution is linear but the code performs several traversals of the linked list. We can avoid reversing the list by having recursion take care of processing the nodes in reverse order. The idea is to recursively reach the end of the linked list and pass the carry information to each parent node as the recursion unfolds. This is demonstrated below in C++:

Output:

Original Linked List: 9 -> 9 -> 9 -> 9 -> 3 -> NULL
Resultant Linked List: 1 -> 0 -> 0 -> 0 -> 0 -> 0 -> NULL

(3 votes, average: 5.00 out of 5)