# 1. Introduction

Rotating a *linked list* involves repositioning its nodes such that the list is shifted by a specified number of positions. For instance, given a linked list *1->2->3->4->5* and a rotation number *2*, the resultant linked list after left rotation would be *3->4->5->1->2*. This task can be accomplished in a linear pass through the list.

# 2. Program Steps

1. Initialize two pointers: *current* and *tail*.

2. Traverse the list to determine its length and to position the *tail* pointer at the last node.

3. Determine the effective number of rotations required (*k* % *length*).

4. If the effective number is zero, no rotation is required. Otherwise, traverse the list again until the (*length* – effective number)th node.

5. Change the next pointer of the *tail* to the *head* and make the *next* of the (*length* – effective number)th node as the new *head*. Finally, set the *next* of the last node to *null*.

# 3. Code Program

```
class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
class LinkedList {
Node head;
// Function to rotate the linked list
public void rotate(int k) {
if (k == 0) return;
Node current = head;
int count = 1;
// Determine length of the list
while (current.next != null) {
current = current.next;
count++;
}
// Determine effective number of rotations required
k = k % count;
if (k == 0) return;
Node tail = current;
current = head;
int i = 1;
// Traverse until reaching the (length - k)th node
while (i < count - k) {
current = current.next;
i++;
}
tail.next = head;
head = current.next;
current.next = null;
}
// Function to print the linked list
void printList() {
Node n = head;
while (n != null) {
System.out.print(n.data + " ");
n = n.next;
}
}
// Function to insert a new Node at the last
public void append(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node last = head;
while (last.next != null) {
last = last.next;
}
last.next = newNode;
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
for (int i = 1; i <= 5; i++) {
list.append(i);
}
System.out.println("Original Linked list:");
list.printList();
list.rotate(2);
System.out.println("\nRotated Linked list:");
list.printList();
}
}
```

### Output:

Original Linked list: 1 2 3 4 5 Rotated Linked list: 3 4 5 1 2

# 4. Step By Step Explanation

1. A *Node* class is defined to create new nodes for the *Linked List*. Each node has a *data* value and a *next* pointer which points to the subsequent node.

2. The *LinkedList* class provides methods to manipulate the linked list, including a *rotate* method.

3. The *rotate* method first determines the length of the list. Then, based on the given rotation count (*k*), the effective number of rotations is calculated. If it's zero, no rotation is needed.

4. The list is traversed until the (*length* – effective rotation count)th node, then pointers are rearranged to achieve the rotation effect.

5. In the *main* method:

a. A *LinkedList* object is created.

b. Nodes with values from 1 to 5 are added to the list.

c. The original list is printed.

d. The list is rotated by 2 positions.

e. The rotated list is printed.

Rotating a *Linked List* by a certain number of positions is a common task in various applications and can be a popular topic during technical interviews.