The O(n) Club: Reverse Linked List II — Now With 100% More Pointer Regret

The O(n) Club: Reverse Linked List II — Now With 100% More Pointer Regret

⚡ TL;DR

A classic linked list headache: given a 1-indexed singly linked list, reverse nodes from left to right (inclusive). On the surface, this sounds easy. But if you aren’t careful, be prepared to break the list in every way imaginable. Here’s the forbidden brute force:

// Brute force (bad):
// 1. Copy nodes into an array
// 2. Reverse [left, right]
// 3. Rebuild list (why?! faster to go outside and touch grass)
 // Instead, reverse in place with pointer jazz hands.

🧠 How Devs Usually Mess This Up

Reversing a whole list is so LeetCode 101. Here, the trap is in the boundaries and connections:

• Off-by-one overload: Since lists are 1-indexed, you’ll move your pointer too few or too many steps and wonder why nodes vanish—or worse, duplicate like rabbits.
• Pointer blender: Reversing nodes is fine, but post-reversal connection? That’s where code goes to break. Real pros forget to save pre-left or after-right; now you have two tails or a circular nightmare.
• Wasting memory: Don’t create new nodes or use arrays! The best solution only juggles pointers—no new data structures, no memory bloat, just raw finger-gymnastics.

🔍 What’s Actually Going On

Picture a children’s toy train. You need to flip cars 3 to 7 but keep the rest in order. Unhook at car 2, spin cars 3 to 7, and reconnect both ends. If left is 1, you’re flipping the front—the engineer is sweating. So, like any seasoned pointer therapist, you stick a trusty dummy node at the front. No more edge-case breakdowns.

The entire trick is walking up to left–1, reversing the segment, and performing surgical reconnect—one O(n) pass, O(1) extra space. No surgery license required.

🛠️ PseudoCode

• Add dummy node: Handles the “reverse-at-head” mess beautifully.

  ListNode dummy = new ListNode(-1);
  dummy.next = head;

• Walk to the node before ‘left’:

  ListNode pre = dummy;
  for (int i = 1; i < left; i++) {
      pre = pre.next;
  }

  Now pre waits faithfully by the front door.

• Reverse between left and right:

  ListNode curr = pre.next;
  ListNode prev = null;
  for (int i = 0; i <= right - left; i++) {
      ListNode next = curr.next;
      curr.next = prev;
      prev = curr;
      curr = next;
  }

  prev becomes the head of the reversed bit. curr is your after-party node.

• Reconnect the reversed segment:

  pre.next.next = curr;
  pre.next = prev;

  Both ends reattached, your list is back on track—no nodes lost or cloned.

• Return dummy.next as the new head.

💻 The Code

// Definition for singly-linked list:
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}
 public ListNode reverseBetween(ListNode head, int left, int right) {
    if (head == null || left == right) return head;
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode pre = dummy;
    for (int i = 1; i < left; i++) {
        pre = pre.next;
    }
    ListNode curr = pre.next;
    ListNode prev = null;
    for (int i = 0; i <= right - left; i++) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    pre.next.next = curr;
    pre.next = prev;
    return dummy.next;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Reversing from the head? Dummy node’s got your back; no more null dereference rage.
• Single node or left == right? Relax! No need for heroics—leave the list alone.
• Edge reversal (at list end!) Code doesn’t care if curr is null.
• Complexity: O(n) time, O(1) space—unless you go recursive and blow the stack. Don’t.

🧠 Interviewer Brain-Tattoo

“Link your pointers like a playlist: if you lose track of the next song, you’re stuck listening to nothing forever.”