The O(n) Club: Linked List Cycle Detection, or Why Tortoises Win at Java

The O(n) Club: Linked List Cycle Detection, or Why Tortoises Win at Java

⚡ TL;DR

Is your linked list accidentally hosting the world’s most boring merry-go-round? Find out by unleashing Floyd’s Tortoise and Hare: two pointers, two speeds, one O(1) solution. Brute force (using HashSet) might get you there, but you’ll waste precious memory and probably feel dead inside. Here’s how the cool kids do it in Java:

// Java cycle detection the O(1) way
public boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

🧠 How Devs Usually Mess This Up

Some folks think a “cycle” only matters if the last node wraps straight back to the head—like boomerangs or bad project requirements. It’s not. Any node that loops to a previously seen node counts. Others stash every node in a HashSet and call it a day, which works but also wastes space and the interviewer’s respect. Remember: LeetCode 141 doesn’t care where the cycle starts, just if there is one. Put that HashSet away and save some heap for later.

🔍 What’s Actually Going On

Think of the linked list as a racetrack.
Slow pointer is your chill, process-minded tortoise—moves one step at a time. Fast pointer is the overzealous hare—moves two steps per tick, thinks meetings are optional. If there’s no loop, hare blazes off the track (null) and the story ends. But if the list loops, then like some twisty Mario Kart map, the hare eventually laps the tortoise somewhere—which means cycle detected!

🛠️ PseudoCode

• Start at the gate: Both pointers begin at head.
  ListNode slow = head; ListNode fast = head;
• Run the race: While fast and fast.next aren’t null (no epic crash)…
• Each round: slow = slow.next;, fast = fast.next.next; (hare gets two espressos per move.)
• Bump check: If slow == fast at any point, congrats, you’re on a loop-de-loop! return true;
• No loops today: If the while loop ends, fast hit null—so no cycle here. return false;

💻 The Code

// ListNode definition for Javaers
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; next = null; }
}
 public class LinkedListCycleDetector {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Yawn-worthy lists: Null head, or just one node? Relax, there’s no loop to find. Don’t dereference yourself into a NPE.
• Cycle location ≠ detection: This only tells you if there’s a cycle—not where it starts (save that for next week’s panic attack).
• Complexity: O(n) time, O(1) space, max two visits per node. Like a minimalist chef—few ingredients, but always delicious.

🧠 Interviewer Brain-Tattoo

“If your code uses more space than a tortoise’s memory, you missed the point. Slow and steady wins the runtime race.”