Rotate the List

Problem Statement

Write a Java program that rotates a circular linked list by k positions, moving the head k nodes forward. A circular linked list is a singly linked list where the last node’s next pointer points to the head, forming a cycle. The rotation shifts the head pointer forward by k nodes, effectively redefining the start of the list while maintaining the circular structure. Test the implementation with different values of k and list sizes, including empty lists, single-node lists, k=0, k equal to the list size, and k greater than the list size. You can visualize this as rotating a ring of numbered beads, where the starting bead (head) moves k positions clockwise, and the ring remains connected.

Input:

• A circular linked list of integers (e.g., 1→2→3→4→1, where 4→1 forms the cycle) and an integer k (number of positions to rotate). Output: The rotated list as a string, listing nodes from the new head until just before it cycles (e.g., "3 4 1 2" after rotating 1→2→3→4→1 by k=2). Constraints:
• The list size is between 0 and 10^5.
• Node values are integers in the range [-10^9, 10^9].
• k is a non-negative integer (k ≥ 0).
• The list may be empty. Example:
• Input: List = 1→2→3→4→1, k = 2
• Output: "3 4 1 2"
• Explanation: Rotates head from 1 to 3, list becomes 3→4→1→2→3.
• Input: List = [], k = 1
• Output: "[]"
• Explanation: Empty list remains empty.
• Input: List = 1→1, k = 3
• Output: "1"
• Explanation: Single-node list is unchanged (rotation wraps around).

Pseudocode

CLASS Node
    SET value to integer
    SET next to Node (null by default)
ENDCLASS

FUNCTION rotateList(head, k)
    IF head is null OR head.next is head THEN
        RETURN head
    ENDIF
    SET length to 1
    SET tail to head
    WHILE tail.next is not head
        INCREMENT length
        SET tail to tail.next
    ENDWHILE
    SET k to k mod length
    IF k equals 0 THEN
        RETURN head
    ENDIF
    SET current to head
    FOR i from 1 to k
        SET current to current.next
    ENDFOR
    SET newHead to current
    SET tail.next to null
    SET current to head
    WHILE current.next is not null
        SET current to current.next
    ENDWHILE
    SET current.next to head
    SET head to newHead
    RETURN head
ENDFUNCTION

FUNCTION toString(head)
    IF head is null THEN
        RETURN "[]"
    ENDIF
    CREATE result as new StringBuilder
    SET current to head
    SET visited as new Set
    WHILE current is not null AND current not in visited
        ADD current to visited
        APPEND current.value to result
        IF current.next is not head THEN
            APPEND " " to result
        ENDIF
        SET current to current.next
    ENDWHILE
    RETURN result as string
ENDFUNCTION

FUNCTION main()
    SET testCases to array of test cases (list values, k)
    FOR each testCase in testCases
        PRINT test case details
        CALL rotateList(testCase.head, testCase.k)
        PRINT rotated list using toString
    ENDFOR
ENDFUNCTION

Algorithm Steps

1. Define a Node class with: a. An integer value. b. A next pointer to the next node.
2. In rotateList: a. If the list is empty or has one node, return head (no rotation needed). b. Find the list length and tail by traversing until tail.next is head. c. Compute effective k as k mod length to handle large k. d. If k=0, return head (no rotation needed). e. Traverse k steps from head to find the new head. f. Break the cycle by setting old tail’s next to null. g. Find new tail (node before new head), set its next to old head. h. Set head to new head, return it.
3. In toString: a. If head is null, return "[]". b. Traverse from head, use a Set to avoid cycling, append values with spaces. c. Return the string representation.
4. In main, test with different list sizes (empty, single-node, multi-node) and k values (0, equal to length, greater than length).

Java Implementation

import java.util.*;

public class RotateCircularLinkedList {
    // Node class for the circular linked list
    static class Node {
        int value;
        Node next;

        Node(int value) {
            this.value = value;
            this.next = null;
        }
    }

    // Rotates the circular linked list by k positions
    public Node rotateList(Node head, int k) {
        if (head == null || head.next == head) {
            return head;
        }
        // Find length and tail
        int length = 1;
        Node tail = head;
        while (tail.next != head) {
            length++;
            tail = tail.next;
        }
        // Normalize k
        k = k % length;
        if (k == 0) {
            return head;
        }
        // Find new head
        Node current = head;
        for (int i = 0; i < k; i++) {
            current = current.next;
        }
        Node newHead = current;
        // Break cycle
        tail.next = null;
        // Find new tail (node before newHead)
        current = head;
        while (current.next != null) {
            current = current.next;
        }
        // Reconnect to form new cycle
        current.next = head;
        head = newHead;
        return head;
    }

    // Converts circular linked list to string
    public String toString(Node head) {
        if (head == null) {
            return "[]";
        }
        StringBuilder result = new StringBuilder();
        Node current = head;
        Set<Node> visited = new HashSet<>();
        while (current != null && !visited.contains(current)) {
            visited.add(current);
            result.append(current.value);
            if (current.next != head) {
                result.append(" ");
            }
            current = current.next;
        }
        return result.toString();
    }

    // Helper class for test cases
    static class TestCase {
        Node head;
        int k;

        TestCase(int[] values, int k) {
            this.k = k;
            if (values.length == 0) {
                head = null;
                return;
            }
            head = new Node(values[0]);
            Node current = head;
            for (int i = 1; i < values.length; i++) {
                current.next = new Node(values[i]);
                current = current.next;
            }
            // Make circular
            current.next = head;
        }
    }

    // Main method to test circular linked list rotation
    public static void main(String[] args) {
        RotateCircularLinkedList rotator = new RotateCircularLinkedList();

        // Test cases
        TestCase[] testCases = {
            new TestCase(new int[]{1, 2, 3, 4}, 2),     // Multi-node, k < length
            new TestCase(new int[]{}, 1),               // Empty list
            new TestCase(new int[]{5}, 3),             // Single node
            new TestCase(new int[]{1, 2, 3}, 3),       // k = length
            new TestCase(new int[]{1, 2, 3, 4, 5}, 7)  // k > length
        };

        // Run test cases
        for (int i = 0; i < testCases.length; i++) {
            TestCase test = testCases[i];
            System.out.println("Test case " + (i + 1) + ":");
            System.out.println("Input list: " + rotator.toString(test.head));
            System.out.println("Rotate by k=" + test.k);
            Node rotated = rotator.rotateList(test.head, test.k);
            System.out.println("Rotated list: " + rotator.toString(rotated) + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1:
Input list: 1 2 3 4
Rotate by k=2
Rotated list: 3 4 1 2

Test case 2:
Input list: []
Rotate by k=1
Rotated list: []

Test case 3:
Input list: 5
Rotate by k=3
Rotated list: 5

Test case 4:
Input list: 1 2 3
Rotate by k=3
Rotated list: 1 2 3

Test case 5:
Input list: 1 2 3 4 5
Rotate by k=7
Rotated list: 3 4 5 1 2

Explanation:

• Test case 1: Rotates 1→2→3→4→1 by k=2, new head=3, outputs "3 4 1 2".
• Test case 2: Empty list, no rotation, outputs "[]".
• Test case 3: Single node 5→5, k=3, no change, outputs "5".
• Test case 4: Rotates 1→2→3→1 by k=3 (length), no change, outputs "1 2 3".
• Test case 5: Rotates 1→2→3→4→5→1 by k=7 (7 mod 5 = 2), new head=3, outputs "3 4 5 1 2".

How It Works

• Node: Stores an integer value and a next pointer.
• rotateList:
  • Handles edge cases: empty list or single node returns unchanged.
  • Finds list length and tail by traversing to the node where next=head.
  • Normalizes k using k mod length to handle large k.
  • If k=0, returns head.
  • Traverses k steps to find new head.
  • Breaks cycle at old tail, reconnects new tail to old head.
• toString: Traverses from head, uses a Set to prevent cycling, returns space-separated string or "[]".
• Example Trace (Test case 1):
  • Input: 1→2→3→4→1, k=2.
  • length=4, tail=4, k=2.
  • current=3 (after 2 steps).
  • newHead=3, tail.next=null → 1→2→3, 4.
  • new tail=2, 2.next=1, head=3.
  • Result: 3→4→1→2→3, outputs "3 4 1 2".
• Main Method: Tests multi-node, empty, single-node, k=length, and k>length cases.

Complexity Analysis Table

Note:

• n is the number of nodes in the list.
• Time complexity: O(n) for rotateList (traverse to find length and new head); O(n) for toString (traverse list).
• Space complexity: O(1) for rotateList (constant pointers); O(n) for toString (StringBuilder and Set).
• Worst case: O(n) time, O(n) space for output with large lists.

✅ Tip: Normalize k using modulo list length to handle large k efficiently. Use a tail pointer to simplify cycle reconnection after rotation.

⚠ Warning: Ensure the cycle is broken and reconnected correctly to avoid infinite loops. Handle edge cases like empty lists or k=0 to prevent unnecessary operations.