Linked List Cycle

This is the problem the whole pattern is named after, and it is often the first question in a linked-list round. The code is six lines. What the interviewer is really testing is whether you can explain why it works.

The problem

You get the head of a singly linked list. Some node's next pointer may point back to an earlier node, so walking the list would go round forever. Return True if the list has such a cycle, and False if walking it eventually reaches None.

• 7 → 4 → 9 → 2 → 5, where node 5 points back to node 4 → True. After 5 you return to 4, then 9, 2, 5, 4… for ever.
• 7 → 4 → 9 → 2 → 5 → None → False. The walk ends after five nodes.

Constraints: up to 10⁴ nodes, any integer values, and the follow-up asks for O(1) extra memory.

Clarifying questions

• Can two nodes hold the same value? Yes. So you must compare node identity, not values. Assume duplicates are possible.
• Can the list be empty? Yes. Return False.
• Can I change the list? Assume no. Marking visited nodes by changing their values or pointers is off the table.
• Do I need to say where the cycle starts? Not here. That is Linked List Cycle II, the natural follow-up.

Approach 1: remember every node

Walk the list and put every node in a set. If you reach a node that is already in the set, you have come back round: there is a cycle. If you reach None, there is not.

1def has_cycle_with_set(head: ListNode | None) -> bool:2    """Remember every node visited; seeing one again means a cycle."""3    seen: set[ListNode] = set()4    node = head5    while node is not None:6        if node in seen:7            return True8        seen.add(node)9        node = node.next10    return False

Nodes can go in a set because Python hashes an object by its identity unless you define __eq__. That is exactly the comparison you want.

Time: O(n). Each node is visited once, and set lookups are O(1) on average. Space: O(n), one entry per node.

The time is already the best possible. The problem is memory. The follow-up asks for O(1) space, and this uses a set that grows with the list. A second brute force, walking from the head again for every new node to check whether it already appeared earlier, uses O(1) space but O(n²) time: 10⁸ steps at n = 10⁴. Each simple answer pays somewhere.

The key insight

You do not need to remember where you have been. You only need to know whether the walk ever ends.

If there is no cycle, a pointer moving two steps at a time reaches None quickly. If there is a cycle, that fast pointer never reaches None. It goes round the loop forever, and so does a slow pointer moving one step at a time. Once both are in the loop, the fast one is chasing the slow one. Each tick, fast moves 2 and slow moves 1, so the distance between them shrinks by exactly 1. A distance that drops by one each tick cannot skip over zero, so they must land on the same node.

So the answer comes from two pointers and one question per tick: "are they on the same node?". There is no set and no memory of the past.

Approach 2: fast and slow pointers

1. Start slow and fast at the head.
2. While fast and fast.next both exist, move slow one step and fast two steps.
3. If they are now the same node, return True.
4. If the loop ends, fast reached the end, so return False.

1def has_cycle(head: ListNode | None) -> bool:2    """Floyd's algorithm: O(n) time, O(1) space."""3    slow = fast = head4    while fast is not None and fast.next is not None:5        slow = slow.next6        fast = fast.next.next7        if slow is fast:8            return True9    return False

Dry run on 7 → 4 → 9 → 2 → 5, where 5 points back to 4:

And on the same list with no cycle, 7 → 4 → 9 → 2 → 5 → None: after tick 1 slow is at 4 and fast at 9; after tick 2 slow is at 9 and fast at 5. Now fast.next is None, so the loop stops and the function returns False.

Time: O(n). Without a cycle, fast reaches the end in about n/2 ticks. With one, slow enters the loop after a ticks (the length of the tail), and the gap closes in fewer than L more ticks, where L is the loop length. Since a + L ≤ n, that is at most n ticks. Space: O(1), two pointers.

Edge cases

• Empty list. fast is None, the loop never runs, and the result is False.
• One node, no cycle. fast.next is None, the loop never runs, False.
• One node pointing to itself. Tick 1: slow moves to the same node, fast moves two steps round the self-loop and is also there. True.
• Two nodes pointing back to the head. Tick 1: slow at node 2, fast back at node 1. Tick 2: slow at node 1, fast at node 1. True.
• Duplicate values. 5 → 7 → 5 → 9 → 5 → None has no cycle, but after two ticks slow and fast sit on two different nodes that both hold 5. Because the check is slow is fast, the equal values do not fool it.

Follow-ups

• "Where does the cycle start?" Keep this loop as phase 1. After they meet, move one pointer back to the head and step both one at a time until they meet again. That is the entrance (Linked List Cycle II).
• "How long is the cycle?" After they meet, hold one pointer still and step the other round, counting, until it comes back. That count is L.
• "Why not speeds 1 and 3?" They would still meet eventually from a common start, but the gap then closes by 2 per tick, so the one-line proof is gone, and the entrance trick in Cycle II depends on the 2-to-1 ratio.