Algo#45: Find middle node from given singly linked list using recursion.

We can find middle node from given linked list in one look of singly linked list using recursion (Ignoring stack removal access).

Following is implementation of above problem in c language.

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

Algo#44: Modify linked list to put nodes alternate from begin & end

To modify linked list to put nodes alternate from begin & end, we will use recursion. So we can access nodes in forward and reverse direction simultaneously. And we don't need to go back and forth to access nodes from begin and end.

Following is implementation of above problem in c language.

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

Algo#20: Tail command implementation

Tail command is used for extracting last n lines from file. This is very common question that we can expect  in any IT interview. To implement tail command we will use queue data structure. 

Following is simple algorithm for tail command implementation with n as parameter (number of last lines to read).

Step 1: Read line from file, and store it into queue.
Step 2: If number of lines in queue exceeds parameter n, then we can delete one line from front. Because we only need to keep n lines in queue.
Step 3: When file reading ends, we have n lines in queue.

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.

Algo#9: Add 2 numbers represented by linked list such that MSD 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, 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.

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.

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.

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.

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.