This post is completed by 1 user

  • 0
Add to List
Medium

187. 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:

Reverse Alternative 'k' nodes in a Linked List.

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.

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