Reverse Alternative 'k' nodes in a Linked List

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:

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

Reverse Alternative ‘k’ nodes in a Linked List.

Related Posts:

Leave a Comment Cancel reply