The O(n) Club: Reorder List: When Your Linked List Needs a Hollywood Makeover (Pointer Edition)

The O(n) Club: Reorder List — When Your Linked List Needs a Hollywood Makeover (Pointer Edition)

⚡ TL;DR

Want to glam up your linked list so it’s L0 → Ln → L1 → Ln-1 and so on? Sure, but you can’t swap node values or call for backup arrays—just honest pointer hustle. Brute force will get you a brute force rejection:

// Nope (brute force):
List<ListNode> nodes = new ArrayList<>();
while (head != null) { nodes.add(head); head = head.next; }
// Try to chain them fancy, but: lots of extra space, cheating, and sadness.

🧠 How Devs Usually Mess This Up

If you reached for an array or swapped node values, you’ve already been eliminated. Problem says: “reorder by changing pointers only.” (No, you can’t sneakily swap values and hope nobody notices.)
No more new lists, no value reassignment, no copy-paste from that one Stack Overflow answer everyone secretly bookmarks. Oh, and edge cases—fail them and your linked list could end up like Schrödinger’s cat: neither alive nor dead, just stuck looping forever.

🔍 What’s Actually Going On

Imagine your playlist: you want to play song 1, then the last song, then the second song, then the second last… you get the vibe. Do this for a linked list, but with pointers doing the limbo.

Three steps, dead simple (in theory):

🛠️ PseudoCode

• Find the middle:
  

  ListNode slow = head, fast = head;
  while (fast != null && fast.next != null) {
      slow = slow.next;
      fast = fast.next.next;
  }

  // ‘slow’ sits in the middle at the finish line.
• Reverse second half:
  

  ListNode prev = null, curr = slow.next;
  while (curr != null) {
      ListNode tmp = curr.next;
      curr.next = prev;
      prev = curr;
      curr = tmp;
  }

  // Now ‘prev’ kicks off your reversed list for the merge dance-off.
• Merge halves:
  

  ListNode first = head, second = prev;
  while (second != null) {
      ListNode tmp1 = first.next, tmp2 = second.next;
      first.next = second;
      second.next = tmp1;
      first = tmp1;
      second = tmp2;
  }

  // Play tag-team pointer wrestling all the way to the center.

💻 The Code

// Java code for O(n) pointer shuffle:
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
 public void reorderList(ListNode head) {
    if (head == null || head.next == null || head.next.next == null) return;
    ListNode slow = head, fast = head;
    // 1. Find the middle
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    // 2. Reverse the second half
    ListNode prev = null, curr = slow.next;
    while (curr != null) {
        ListNode nextTmp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTmp;
    }
    slow.next = null; // Break the list
    // 3. Merge halves
    ListNode first = head, second = prev;
    while (second != null) {
        ListNode tmp1 = first.next;
        ListNode tmp2 = second.next;
        first.next = second;
        second.next = tmp1;
        first = tmp1;
        second = tmp2;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Tiny lists: If the list is size 0, 1, or 2, leave it be. It’s already as reordered as it gets.
• Lost nodes: Nasty off-by-one errors (especially with odd/even lengths) will have nodes vanish into the void.
• Cycle creation: One careless .next and you’ve built an infinite loop. Always null out split points.
• Performance: O(n) time, O(1) space—you’re working like a seasoned pointer acrobat.

🧠 Interviewer Brain-Tattoo

“Making a sandwich, pointer-style: Take a slice from the front, then one from the back, and repeat until you hit pure algorithmic satisfaction—no crumbs left behind.”