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:
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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class ReverseAlternateKNodes { | |
public static void main(String[] args) throws java.lang.Exception { | |
LinkedListT a = new LinkedListT(); | |
for (int i = 1; i <= 12; i++) { | |
a.addAtEnd(i); | |
} | |
System.out.print("Original Link List 1 : "); | |
a.display(a.head); | |
int k = 2; | |
System.out.println("\n Recursion with 2k nodes where k = " +k); | |
Node n = a.reverseAlter2KNodes(a.head, k); | |
a.display(n); | |
LinkedListT b = new LinkedListT(); | |
for (int i = 1; i <= 12; i++) { | |
b.addAtEnd(i); | |
} | |
System.out.print("\nOriginal Link List 2 : "); | |
b.display(b.head); | |
k=3; | |
System.out.println("\n Recursion with k nodes where k=" +k); | |
n = b.reverseAlterKNodes(b.head, k, true); | |
b.display(n); | |
} | |
} | |
class Node { | |
public int data; | |
public Node next; | |
public Node(int data) { | |
this.data = data; | |
this.next = null; | |
} | |
} | |
class LinkedListT { | |
public Node head; | |
public LinkedListT() { | |
head = null; | |
} | |
public Node reverseAlterKNodes(Node head, int k, Boolean odd) { | |
int x = k; | |
Node moving = head; | |
Node head_prev = null; | |
Node head_next = null; | |
//check if odd = true then we will reverse first k nodes | |
if (odd) { | |
while (x > 0 && moving != null) { | |
head_next = moving.next; | |
moving.next = head_prev; | |
head_prev = moving; | |
moving = head_next; | |
x—; | |
} | |
if (head != null) | |
head.next = reverseAlterKNodes(moving, k, false); | |
return head_prev; | |
} | |
//check if odd = false then we will not reverse next k nodes | |
else { | |
Node prev = moving; | |
while (x > 1 && moving != null) { | |
moving = moving.next; | |
x—; | |
} | |
if (moving != null) { | |
moving.next = reverseAlterKNodes(moving.next, k, true); | |
} | |
return prev; | |
} | |
} | |
public Node reverseAlter2KNodes(Node head, int k) { | |
//process 2K nodes at a time | |
//reverse till k nodes and set the the pointer to k+1 | |
int x = k; | |
Node moving = head; | |
Node head_prev = null; | |
Node head_next = null; | |
while (x > 0 && moving != null) { | |
head_next = moving.next; | |
moving.next = head_prev; | |
head_prev = moving; | |
moving = head_next; | |
x—; | |
} | |
if (head != null) | |
head.next = moving; | |
x = k; | |
while (x > 1 && moving != null) { | |
moving = moving.next; | |
x—; | |
} | |
if (moving != null) { | |
moving.next = reverseAlter2KNodes(moving.next, k); | |
} | |
return head_prev; | |
} | |
public void addAtEnd(int data) { | |
Node n = new Node(data); | |
if (head == null) { | |
n.next = head; | |
head = n; | |
} else { | |
Node currNode = head; | |
while (currNode.next != null) { | |
//System.out.print("—->" + currNode.data); | |
currNode = currNode.next; | |
} | |
currNode.next = n; | |
} | |
} | |
public void display(Node head) { | |
Node currNode = head; | |
while (currNode != null) { | |
System.out.print("->" + currNode.data); | |
currNode = currNode.next; | |
} | |
} | |
} | |
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