Linked List Cycle

Problem

You are given the head of a singly linked list. Determine whether the list contains a cycle — that is, whether some node’s next pointer points back to an earlier node in the list, so that walking the list would loop forever instead of reaching None.

Return True if a cycle exists, False otherwise.

(LeetCode’s test harness describes the cycle with an index pos, but your function only receives head — pos is not a parameter.)

Examples

• Input: 3 -> 2 -> 0 -> -4, where -4.next points back to node 2 → Output: True Walking the list revisits node 2 forever.
• Input: 1 -> 2, where 2.next points back to node 1 → Output: True The tail loops back to the head.
• Input: 1 -> None → Output: False The walk terminates at None, so there is no cycle.

Constraints

• Number of nodes is in [0, 10^4].
• -10^5 <= Node.val <= 10^5
• Follow-up: solve it with O(1) memory.

Think about it first

TL;DR

Floyd’s tortoise-and-hare (fast/slow pointers) — O(n) time, O(1) space.

Approach 1 — Brute force: remember every node you visit

Walk the list and record each node in a set. If you ever step onto a node that is already in the set, you have looped; if you reach None, you haven’t.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

from typing import Optional


class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        seen = set()
        node = head
        while node:
            if node in seen:
                return True
            seen.add(node)
            node = node.next
        return False

Complexity: O(n) time, O(n) space.

This actually passes the constraints (10^4 nodes is tiny) — what kills it is the follow-up: the interviewer wants O(1) memory, and the set stores every node.

Approach 2 — Floyd’s cycle detection (fast & slow pointers)

The insight: if two runners move through the list at different speeds (1 step vs. 2 steps), then in a cycle the fast runner gains one node on the slow runner every step. The gap between them shrinks by exactly 1 each iteration, so it must hit 0 — they meet. If there is no cycle, the fast runner simply falls off the end at None.

This is Floyd’s cycle-detection algorithm (“tortoise and hare”): a classical technique that detects a cycle in any sequence generated by repeatedly applying a function, using two iterators at different speeds and constant memory.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

from typing import Optional


class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                return True
        return False

Walkthrough on 3 -> 2 -> 0 -> -4, with -4.next = 2:

On the cycle-free list 1 -> None: fast.next is None immediately, the loop body never runs, return False.

Complexity: O(n) time — the slow pointer takes at most n steps before the fast pointer either meets it or exits. O(1) space.

Common pitfalls

• Comparing values instead of node identity. Values can repeat in a valid acyclic list; compare nodes with is (or rely on set membership of node objects), never == on val.
• Advancing fast two steps without first checking both fast and fast.next — on an even-length acyclic list you’ll call .next on None.
• Checking slow is fast before moving them: they start equal at head, so a pre-move check returns True on every non-empty list.
• Forgetting the empty list: with head is None, the loop condition handles it — don’t add code that dereferences head first.

Pattern takeaway

Fast/slow pointers turn “does this walk ever repeat?” into a constant-space check: unequal speeds guarantee a meeting inside any loop and a clean None exit otherwise. Reach for this whenever a linked structure (or any iterated function, like in Find the Duplicate Number) might loop and you can’t afford a visited-set.