Write a Java program to Rotate a Linked List


The code provided is an implementation of a Rotate_LinkedList class in Java that rotates a linked list by k positions. The linked list is represented using a Node class with an integer data field and a next pointer. The Rotate_LinkedList class has the following methods:

  • rotate(int k): This method rotates the linked list by k positions. It first checks if k is 0, in which case no rotation is needed and it returns early. Then, it iterates through the linked list to find the kth node from the head. After that, it updates the next pointer of the last node in the original list to point to the head, and updates the head to be the next node after the kth node. Finally, it sets the next pointer of the kth node to null to mark the end of the rotated list.
  • push(int val) : This method pushes a new node with the given value to the front of the linked list. It creates a new node with the given value, sets its next pointer to the current head, and updates the head to be the new node.
  • printList(): This method prints the values of the nodes in the linked list, separated by a space.
  • main(String args[]): This is the main method that creates an instance of the Rotate_LinkedList class, pushes values from 100 to 10 to the linked list, prints the original linked list, calls the rotate method with k=6, and prints the rotated linked list.

Note: The implementation assumes 1-based indexing for rotating the linked list, meaning the first position is index 1. If you want to use 0-based indexing, you need to adjust the implementation accordingly. Also, the implementation does not handle cases where k is larger than the size of the linked list, so make sure to handle such cases if needed.

Source Code

class Rotate_LinkedList
{
	Node head;
	class Node
	{
		int data;
		Node next;
		Node(int d)
		{
			data = d;
			next = null;
		}
	}
	void rotate(int k)
	{
		if (k == 0)
			return;
 
		Node current = head;
 
		int count = 1;
		while (count < k && current != null)
		{
			current = current.next;
			count++;
		}
 
		if (current == null)
			return;
 
		Node kthNode = current;
		while (current.next != null)
		{
			current = current.next;
		}
		current.next = head;
		head = kthNode.next;
		kthNode.next = null;
	}
	void push(int val)
	{
		Node new_val = new Node(val);
		new_val.next = head;
		head = new_val;
	}
 
	void printList()
	{
		Node temp = head;
		while (temp != null)
		{
			System.out.print(temp.data + " ");
			temp = temp.next;
		}
		System.out.println();
	}
 
	public static void main(String args[])
	{
		Rotate_LinkedList llist = new Rotate_LinkedList();
 
		for (int i = 100; i >= 10; i -= 10)
		{
			llist.push(i);
		}
 
		System.out.print("Given LinkedList : ");
		llist.printList();
 
		llist.rotate(6);
 
		System.out.print("Rotated LinkedList : ");
		llist.printList();
	}
}

Output

Given LinkedList : 10 20 30 40 50 60 70 80 90 100
Rotated LinkedList : 70 80 90 100 10 20 30 40 50 60

Example Programs