Linked List Cycle (LeetCode 141)

The problem

You get the head of a singly linked list. Some node’s next may point back to an earlier node, which makes the list loop forever. Return True if the list has a cycle, False if it ends.

Input:  3 -> 2 -> 0 -> -4
             ^         |
             +---------+     (the tail -4 points back to node 2)
Output: True

Following next from -4 goes back to 2, so you never reach the end.

How to think about it

Start with brute force. Walk the list and store every node you visit in a set. If you ever see a node twice, there is a cycle. If you reach None, there is not. That is O(n) time but O(n) extra space, and the follow-up always asks for O(1).

You cannot just walk and wait. Without memory, a single pointer in a cycle runs forever and never “knows” it is looping. You need something that turns “loops forever” into a condition you can test.

The key insight: two runners on a circular track must meet. Move s one step and f two steps per tick. If the list ends, f hits None first and you return False. If there is a cycle, both pointers eventually enter it. Once inside, f gains exactly one node per tick on s, so the gap between them shrinks by one each tick and must reach zero. They land on the same node, and that collision is your proof of a cycle.

Which pattern is this? Fast & slow pointers (Floyd’s tortoise and hare). The tell is “detect a loop in a sequence with O(1) memory”.

Approach

1. Start s and f at head.
2. While f and f.next exist, move s one step and f two steps.
3. After each move, if s is f (the same node object), return True.
4. If the loop exits, f reached the end, so return False.

Solution

def has_cycle(head):
    s = f = head
    while f and f.next:                # fast hit the end -> no cycle
        s = s.next; f = f.next.next
        if s is f: return True         # fast lapped slow -> cycle
    return False
# has_cycle([3,2,0,-4] with tail linked to node index 1) -> True

Dry run

On the example, the cycle is 2 -> 0 -> -4 -> 2. Values shown are the nodes each pointer sits on after the step:

They meet on node -4 after three steps, so the answer is True. On 1 -> 2 with no cycle, after one step f is None and the function returns False.

Complexity

• Time: O(n). Before the cycle, slow takes at most n steps. Inside the cycle, the gap closes by one per tick, so fast catches slow within one lap.
• Space: O(1). Two pointers, no visited set.

Edge cases and pitfalls

• Empty list or a single node with no cycle: the loop condition fails at once and returns False.
• A single node pointing to itself: after one step both pointers are on it, so it returns True.
• Compare nodes, not values. Use is. Two different nodes can hold the same value, and s.val == f.val would report false cycles.
• Check after moving, not before. Both pointers start on head, so checking s is f first would return True immediately.
• Null safety. f.next.next needs both f and f.next to exist, which is why the loop guards both.

Related problems

• Linked List Cycle II (LeetCode 142): after the meeting, find where the cycle starts.
• Happy Number (LeetCode 202): the same detection on a sequence of numbers instead of nodes.
• Find the Duplicate Number (LeetCode 287): an array disguised as a linked list with a cycle.