Reverse Alternative ‘k’ nodes in a Linked List.

by

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.

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

Related Posts: