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


def hasCycle(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 passes the constraints (10^4 nodes is small). The limitation is the follow-up, which asks for O(1) memory: the set stores every node.

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

The insight: if two pointers move through the list at different speeds (1 step vs. 2 steps), then inside a cycle the fast pointer gains one node on the slow pointer every step. The gap shrinks by exactly 1 each iteration, so it must reach 0 and the pointers meet. If there is no cycle, the fast pointer reaches None and the walk ends.

The example list forms a cycle from the tail back to node 2:

flowchart LR
    A[3] --> B[2]
    B --> C[0]
    C --> D[-4]
    D --> B

This is Floyd’s cycle-detection algorithm (“tortoise and hare”): a standard 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


def hasCycle(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.