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, Most Significant Digit (MSD) is representing head of linked list. E.G 321 can be represented as : 3->2->1 , 52 can be represented as : 5->2
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. One thing to note here is, when list are represented like this, actually we are having tough problem to solve because 2 list can be of different size. One way to convert this problem in easy one is by reversing both list, then apply algorithm of adding list when header represent LSD. But what if we have been asked that we can't modify given 2 list at all. Here comes recursion to help us.
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. One thing to note here is, when list are represented like this, actually we are having tough problem to solve because 2 list can be of different size. One way to convert this problem in easy one is by reversing both list, then apply algorithm of adding list when header represent LSD. But what if we have been asked that we can't modify given 2 list at all. Here comes recursion to help us.
Following is simple recursive algorithm for adding 2 numbers represented by linked list such that MSD of number is head of linked list. Technique same as post order traversal, process remaining (child) list first before adding current node.
Assume that size(first list) >= size(second list) , this assumption can be taken without any loss of generality of our algorithm because we can always pass list to our algorithm such that assumption is perfectly valid.
Assume that size(first list) >= size(second list) , this assumption can be taken without any loss of generality of our algorithm because we can always pass list to our algorithm such that assumption is perfectly valid.
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 remaining digits from both list recursively same way. Don't forget to get carry of remaining addition.
2.2.1: If both list have same size, then add digit from first list, digit from second list and carry of remaining list addition.
2.2.2: If size(first list) > size(second list), then add digit from first list and carry of remaining list addition.
2.3: Get resultant digit of this addition by taking modulo 10 and put it inside newly created node.
2.4: Attach list built from recursion to current resultant list.
2.5: [CRITICAL STEP] Fill reverse carry so that previous iteration can use it.
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 remaining digits from both list recursively same way. Don't forget to get carry of remaining addition.
2.2.1: If both list have same size, then add digit from first list, digit from second list and carry of remaining list addition.
2.2.2: If size(first list) > size(second list), then add digit from first list and carry of remaining list addition.
2.3: Get resultant digit of this addition by taking modulo 10 and put it inside newly created node.
2.4: Attach list built from recursion to current resultant list.
2.5: [CRITICAL STEP] Fill reverse carry so that previous iteration can use it.
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.
No comments:
Post a Comment
Write your comment here.