Linked List Cycle

EASY✓ CHIP-TIMEDLC #141 — FULL STATEMENT ↗

The drill: Detect whether a singly linked list loops back into itself instead of terminating at null. A flat list can't encode a loop by itself, so each case also carries the index the tail wraps back to (−1 for none) — an honest stand-in for the hidden judge that wires the loop in the original problem.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A singly linked list might terminate normally at null, or its tail might loop back and point into some earlier node in the list, sending a naive walk in endless circles.

The job is to report whether that loop exists at all — a simple true or false, with no need to say where the loop begins.

Since a flat list of values can't represent a loop by itself, each case on this course also carries the index the tail wraps back to, using −1 to mean no cycle at all; that's this site's honest stand-in for the hidden setup the classic problem relies on.

EX 01

head = [10, 20, 30, 40] · pos = 1

→ true

TAIL WRAPS INTO THE MIDDLE

EX 02

head = [5] · pos = -1

→ false

SINGLE NODE, NO CYCLE

EX 03

head = [5] · pos = 0

→ true

SINGLE NODE POINTS TO ITSELF

list holds up to a few thousand nodes before any looping
cycle position, when present, can point to any earlier node including the head
a value of −1 for the cycle position means the list truly ends at null
answer is a single true/false, not the cycle's location

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A linear walk that stops at null only works when the list actually ends — a cycle never produces that null, so a naive scan spins forever. What could a walk remember about the ground it has already covered?

HINT 2 THE STRUCTURE

A set of visited node identities catches the repeat the instant it happens, at the cost of memory proportional to the list. Is there a way to notice a repeat using only a couple of pointers and no extra storage?

HINT 3 ONE STEP FROM THE ANSWER

Send two pointers down the list at different speeds — one step at a time, the other two. A cycle forces the faster pointer to lap the slower one and land on the same node; an acyclic list just lets the faster pointer run off the end first.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE LAP DETECTORPATTERN · TORTOISE AND HARElist = 10 → 20 → 30 → 40 · tail wraps to index 1

STEP 1

List 10→20→30→40, and the tail (node 40) wraps back to node 20 (index 1) instead of ending — a cycle. Send two pointers at different speeds.

STEP 1 / 5 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/linked-list-cycle.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def hasCycle(self, head: Optional[ListNode], pos: int) -> bool:
        if pos != -1:
            nodes = []
            n = head
            while n:
                nodes.append(n)
                n = n.next
            if nodes:
                nodes[-1].next = nodes[pos]

        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                return True
        return False

TIME O(N)SPACE O(1)PYTHON · RACE PACE · 18 LN

class Solution:
    def hasCycle(self, head: Optional[ListNode], pos: int) -> bool:
        # the judge's loop convention: wire the tail back to index `pos`
        # before running the actual detection (-1 means no cycle at all)
        if pos != -1:
            nodes = []
            n = head
            while n:
                nodes.append(n)
                n = n.next
            if nodes:
                nodes[-1].next = nodes[pos]

        seen = set()
        n = head
        while n:
            if id(n) in seen:
                return True
            seen.add(id(n))
            n = n.next
        return False

TIME O(N)SPACE O(N)PYTHON · TRAINING PACE · 21 LN

class Solution {
    public boolean hasCycle(ListNode head, int pos) {
        if (pos != -1) {
            List<ListNode> nodes = new ArrayList<>();
            for (ListNode n = head; n != null; n = n.next) nodes.add(n);
            if (!nodes.isEmpty()) nodes.get(nodes.size() - 1).next = nodes.get(pos);
        }

        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;
    }
}

TIME O(N)SPACE O(1)JAVA · RACE PACE · 17 LN

class Solution {
    public boolean hasCycle(ListNode head, int pos) {
        if (pos != -1) {
            List<ListNode> nodes = new ArrayList<>();
            for (ListNode n = head; n != null; n = n.next) nodes.add(n);
            if (!nodes.isEmpty()) nodes.get(nodes.size() - 1).next = nodes.get(pos);
        }

        Set<ListNode> seen = new HashSet<>();
        for (ListNode n = head; n != null; n = n.next) {
            if (!seen.add(n)) return true;
        }
        return false;
    }
}

TIME O(N)SPACE O(N)JAVA · TRAINING PACE · 15 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED