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.

// Please, put the coffee down and don't copy this
public ListNode rotateRight(ListNode head, int k) {
    while (k-- > 0) {
        if (head == null || head.next == null) return head;
        ListNode prev = null, curr = head;
        while (curr.next != null) {
            prev = curr;
            curr = curr.next;
        }
        prev.next = null;
        curr.next = head;
        head = curr;
    }
    return head;
}

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.
• Count length and get the tail:

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

• Effective rotation: k = k % n; (You’re welcome.) If k == 0, return head—no need for pointer gymnastics.
• Circle up: tail.next = head;
• Find new tail at n – k – 1 steps:

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

• Break the circle: newTail.next = null;
• Return newHead: List rotated, dance concluded.

💻 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 < 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?

🧠 Interviewer Brain-Tattoo

“If you wrote O(k × n) here, you’re banned from pointer-based jokes for a year.”