How to Optimize Linked List Rotation in Java: A Guide to Fast Algorithms

---

Rotating a linked list to the right by k positions is a common problem — and a perfect example to demonstrate how brute-force logic can evolve into a more elegant and efficient solution. Here's a breakdown of both approaches and how to go from O(n * k) to O(n).

---

🔁 Brute Force Approach (O(n * k))

In the brute-force method, we rotate the list by moving the last node to the front — and we repeat this k times.

🚧 Code:

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) return head;

        for (int i = 0; i < k; i++) {
            ListNode curr = head;
            ListNode prev = null;

            while (curr.next != null) {
                prev = curr;
                curr = curr.next;
            }

            prev.next = null;
            curr.next = head;
            head = curr;
        }

        return head;
    }
}

🔍 Time Complexity:

• Each rotation: O(n)

• Total time: O(n * k)

• Works fine for small values of k, but inefficient when k is large.

---

⚡ Optimized Approach (O(n) Time)

After understanding the brute-force limitations, we can optimize this with a smarter trick: by converting the list into a circular linked list, and then breaking it at the right place.

---

🧠 Key Insights:

1. Find the length of the list and connect the tail to the head to make it circular.

2. If k is greater than the length, the list will rotate back to the same position every length steps. So, we only need to do k % length rotations.

3. To rotate the list:

   • Compute:
     stepsToNewTail = length - (k % length)

   • Move that many steps from the head to find the new tail.

   • The new head is newTail.next.

4. Break the circular link by doing newTail.next = null.

---

✅ Example:

If length = 5 and k = 7,
then effective rotations = 7 % 5 = 2
→ New tail will be at node 3 (step 3 from head)
→ New head will be node 4

---

🧩 Optimized Code (O(n)):

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) return head;

        // Step 1: Get length and old tail
        ListNode oldTail = head;
        int length = 1;
        while (oldTail.next != null) {
            oldTail = oldTail.next;
            length++;
        }

        // Step 2: Make circular
        oldTail.next = head;

        // Step 3: Normalize k
        k = k % length;
        int stepsToNewTail = length - k;

        // Step 4: Find new tail
        ListNode newTail = head;
        for (int i = 0; i < stepsToNewTail - 1; i++) {
            newTail = newTail.next;
        }

        // Step 5: Set new head and break the circle
        ListNode newHead = newTail.next;
        newTail.next = null;

        return newHead;
    }
}

---

🧠 Takeaway

• Rotating a linked list is a great example of when a brute-force solution helps us understand the problem — but optimization gives us performance and elegance.

• Turning the list into a circular one and breaking it at the right spot is a smart and efficient technique to keep in your DSA toolbox.

---

If you liked this breakdown, follow for more posts like this! 🔁💡