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:

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;
}
}
}

view raw
ReverseAlternateKNodes.java
hosted with ❤ by GitHub


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: