Reverse Alternative ‘k’ nodes in a Linked List.

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.

Run This Code

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