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.