Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Reverse Alternative ‘k’ nodes in a Linked List.

Objec­tive: Given a linked list and a num­ber ‘k’, write an algo­rithm to reverse alter­nate ‘k’ nodes in the linked list.

This prob­lem was asked in the Microsoft and Ama­zon interviews.

Exam­ple:

Reverse Alternative 'k' nodes in a Linked List.

Reverse Alter­na­tive ‘k’ nodes in a Linked List.

Approach:

Recur­sion is the key here. Solu­tion will be quite sim­i­lar to “Reverse a Linked List in groups of given size ‘K’” with some mod­i­fi­ca­tions. We can solve it in two methods–

  • Tak­ing ‘k’ nodes for a iteration.
  • Tak­ing ‘2k’ nodes for a iter­a­tion.

Method 1: Tak­ing ‘k’ nodes for a iteration.

  • Take ‘k’ nodes at a time for one iter­a­tion and call rest of the recursively.
  • In alter­nate iterations–
    • Reverse the ‘k’ nodes.
    • Skip the ‘k’ nodes.
  • we use boolean vari­able to iden­tify when to reverse OR Skip nodes.

Method 2: Tak­ing ‘2k’ nodes for a iteration.

  • Take 2’k’ nodes at a time for one iter­a­tion and call rest of the recursively.
  • In every iteration–
    • Reverse the first ‘k’ nodes.
    • Skip the next ‘k’ nodes.

Look at the code for bet­ter understanding.

Com­plete Code:

Out­put:

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

You may also like...