The O(n) Club: Rotate List: How to Not Tie Your Pointers in Knots

The O(n) Club: Rotate List—How to Not Tie Your Pointers in Knots

⚡ TL;DR

Rotate a singly linked list right by k spots. Please don’t move the tail to head k times like it’s medieval penalty hour—that’s O(k × n) and your CPU didn’t sign up for cardio.

Want your app finished before the next version of Java? Scroll on. 🚀

🧠 How Devs Usually Mess This Up

Classic rookie bloopers include:

Ignoring effective rotation: Rotating 10,000 places on a 5-node list is… still 0. Modulo is your friend. Use it.
Pointers gone wild: Swinging fast/slow pointers like they’re live wires, ending up in the Bermuda Triangle of NullPointerExceptions or infinite cycles.
Neglecting edge-cases: Null list? One node? Zero moves? Skipped like your boss at daily standup.

🔍 What’s Actually Going On

Imagine a conga line at your office party. Rotating right by k means the last k dancers dash to the front, conga-style, without trampling someone’s feet (or your pointer integrity). Real magic: just snap the circle at the right point. If you spin the full length—or a multiple—nobody moves, no matter how often you clap.

How do you handle that without breaking the dance floor?

Count nodes: So you know when you’re back at the start.
Connect tail to head: Form a circle, keep the party going.
Find the spot to break: Where the last k join the front.
Break the link: Resume boring work in O(n) time.

🛠️ PseudoCode

Check for base cases: Return head if empty, only one node, or k == 0.
Effective rotation: k = k % n; (You’re welcome.) If k == 0, return head—no need for pointer gymnastics.
Circle up: tail.next = head;
Break the circle: newTail.next = null;
Return newHead: List rotated, dance concluded.

Find new tail at n – k – 1 steps:

ListNode newTail = head;
for (int i = 0; i &lt; n - k - 1; i++) {
    newTail = newTail.next;
}
ListNode newHead = newTail.next;

Count length and get the tail:

int n = 1;
ListNode tail = head;
while (tail.next != null) {
    tail = tail.next;
    n++;
}

💻 The Code

// ListNode class: class ListNode { int val; ListNode next; }
public ListNode rotateRight(ListNode head, int k) {
    if (head == null || head.next == null || k == 0) return head;
    ListNode tail = head;
    int n = 1;
    while (tail.next != null) {
        tail = tail.next;
        n++;
    }
    k = k % n;
    if (k == 0) return head;
    tail.next = head;
    ListNode newTail = head;
    for (int i = 0; i &lt; n - k - 1; i++) {
        newTail = newTail.next;
    }
    ListNode newHead = newTail.next;
    newTail.next = null;
    return newHead;
}

⚠️ Pitfalls, Traps & Runtime Smacks

Rookie math fails: Don’t skip k % n, or you’ll be rotating for eternity. (And your interviewer will, too.)
Circular misery: Forgetting newTail.next = null means the list now circles the drain forever.
Edge-case sabotage: Handle zero, one, and giant k or you’ll be debugging in your sleep.
Performance? Two clean O(n) passes and a smug O(1) space. Who needs more?