# 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 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
```