Objective: Given a linked list and a number ‘k’, write an algorithm to reverse alternate ‘k’ nodes in the linked list.
This problem was asked in the Microsoft and Amazon interviews.
Example:
Approach:
Recursion is the key here. Solution will be quite similar to “Reverse a Linked List in groups of given size ‘K’” with some modifications. We can solve it in two methods-
- Taking ‘k’ nodes for a iteration.
- Taking ‘2k’ nodes for a iteration.
Method 1: Taking ‘k’ nodes for a iteration.
- Take ‘k’ nodes at a time for one iteration and call rest of the recursively.
- In alternate iterations-
- Reverse the ‘k’ nodes.
- Skip the ‘k’ nodes.
- we use boolean variable to identify when to reverse OR Skip nodes.
Method 2: Taking ‘2k’ nodes for a iteration.
- Take 2’k’ nodes at a time for one iteration and call rest of the recursively.
- In every iteration-
- Reverse the first ‘k’ nodes.
- Skip the next ‘k’ nodes.
Look at the code for better understanding.
Complete Code:
Output:
Original Link List 1 : ->1->2->3->4->5->6->7->8->9->10->11->12 Recursion with 2k nodes where k = 2 ->2->1->3->4->6->5->7->8->10->9->11->12 Original Link List 2 : ->1->2->3->4->5->6->7->8->9->10->11->12 Recursion with k nodes where k=3 ->3->2->1->4->5->6->9->8->7->10->11->12