Algo#8: Add 2 numbers represented by linked list such that LSD of number is head of linked list.

Numbers represented by link list means each digit of number is occupying 1 node in linked list. Obviously your next question would be how number is stored, is it head to tail or tail to head in linked list. Both ways are right depending on purpose of your application. Lets say, Least Significant Digit (LSD) is representing head of linked list. E.G 321 can be represented as : 1->2->3

So coming to given problem. We have been given 2 such linked list, and our task at hand is to sum up these 2 numbers and store its addition in one such link list.

Following is simple algorithm for adding  2 numbers represented by linked list such that LSD of number is head of linked list.

Step 1: If both current list are empty, then resultant list is also empty.
Step 2: Otherwise, any one or both list are not empty.
        2.1: Make new resultant list node with its value as zero.
        2.2: Add initial digit from both current list (Add zero if any list is empty), along with carry from previous addition (if any else add zero).
        2.3: Get resultant digit of this addition by taking modulo 10 and put it inside newly created node and keep carry ready to be passed to next iteration.
       2.4: Add remaining digits from both list recursively same way. Don't forget to pass carry of last addition.
       2.5: Attach list built from recursion to current resultant list node.

Following is implementation of above algorithm in c language.

Please write comments if you find anything wrong or you want to add something more related to this topic.