The O(n) Club: Middle of the Linked List—How to Outsmart a Conga Line (in Java)

The O(n) Club: Middle of the Linked List—How to Outsmart a Conga Line (in Java)

⚡ TL;DR

Need to find the middle of a singly linked list? Don’t bother counting, just use two pointers—the slow one strolls, the fast one sprints. When the fast one faceplants at the end, the slow one’s at the middle. For even-length lists, return the second middle (per LeetCode’s twisted preference).

// Java's two-pointer party
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}
return slow; // Middle node, no counters, no drama

🧠 How Devs Usually Mess This Up

Old-school panic: “Just count nodes, divide by two, walk again!” Welcome to the world’s slowest race. Others return the first middle node in even-length lists—nope, specs want the second (because why not). Bonus points if you tried to copy everything into an array or deployed recursive sorcery for zero reason.

🔍 What’s Actually Going On

Picture a conga line at a coder party. Slow Sam hops one person at a time; Fast Fiona leapfrogs two. The moment Fast Fiona tumbles off the dancefloor (list end), Slow Sam’s left right in the middle. For even numbers, Sam is polite and steps into the second of the central pair. All done with a single pass—unlike your last team’s deployments.

🛠️ PseudoCode

• Set slow and fast pointers to head.
  

  ListNode slow = head;
  ListNode fast = head;

• Move through the list:
  While fast and fast.next aren’t null:
  

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

• When loop exits, slow points at the middle (second middle for even lists).
• Return slow. That’s your champagne toast.

💻 The Code

// ListNode class for Java fans
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}
 public ListNode middleNode(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Returning the wrong node: For even lists, must return the second middle. Specs don’t lie.
• Counting before running: Double passes = CPU sadness. This is a one-loop dance.
• Null-pointer clown show: If head is null, please just return null. Avoid drama.
• Wasting space: Don’t use arrays, lists, or a diary to track nodes. This pattern is O(1) space.
• Performance debrief: Single pass = O(n) time. O(1) space. Clean as a whistle.

🧠 Interviewer Brain-Tattoo

“A slow pointer and a fast pointer walk into a list. Only one gets the job.”