• The number of nodes in the list is in the range [0, 10⁴]
• -10⁵ <= Node.val <= 10⁵
• Can you solve it using O(1) memory?

We're given a singly linked list and asked one yes/no question: does it contain a cycle? A cycle means some node's next points back to a node we've already passed, so following next forever never reaches an end — you just go round and round. A normal list ends at a null. A cyclic list has no null to fall off. The danger is obvious: if we naively walk it looking for the end, and there is a loop, we are the ones who never stop. How do we detect an endless loop without getting stuck in it?

Keep a record of where you've been. Walk the list and drop each node into a hash set — a structure that answers "have I already stored this?" in roughly constant time. At every new node, ask the set whether you've seen it before. If yes, you've circled back onto an old node, so a cycle exists. If you instead reach a null, the list ends and there's no cycle.

seen = set()
curr = head
while curr:
    if curr in seen:
        return True      # walked onto a node we already visited
    seen.add(curr)
    curr = curr.next
return False             # fell off the end, no loop

This works and runs in O(N) time, but it pays O(N) extra memory — in the worst case it remembers every node in the list. The question that unlocks the better answer: can we tell a loop exists without writing down where we've been?

Reuse the exact walk from Middle of the Linked List: a slow pointer taking one step per turn and a fast pointer taking two, both starting at the head. In that problem the double-speed pointer let us find a position. Here the same setup answers a completely different question, and it hinges on one observation about what the fast pointer runs into.

If the list is a straight line with an end, fast — being quicker — reaches the null and we stop: no cycle, just like before. But if there is a loop, fast can never leave it; it's trapped going round. slow eventually enters that same loop too. Now both are circling inside the loop, and fast is gaining on slow at a steady rate.

This is the part worth proving to yourself, not just believing. Once both pointers are inside the loop, look at the gap between them — the number of steps from fast forward to slow around the circle. Each turn, slow advances 1 and fast advances 2, so fast closes the gap by exactly one node per turn. A gap that shrinks by one every single turn, and can never overshoot (it drops 3→2→1→0, it cannot jump from 1 straight past 0), must eventually hit zero. Gap zero means both pointers are on the very same node — a collision. Crucially this holds no matter how big the loop is: the gap starts at some finite number less than the loop length and ticks down to 0. So inside a loop, meeting is not luck — it's forced.

slow = head
fast = head
while fast and fast.next:     # same two-step safety guard as before
    slow = slow.next          # one step
    fast = fast.next.next     # two steps
    if slow == fast:          # same physical node → they collided
        return True
return False                  # fast reached a null → no loop

No memory used, and the loop was caught in three turns.

Notice what changed from the previous problem and what didn't: the machinery — slow-by-one, fast-by-two, the two-step guard — is identical. Only the question changed. That reuse is the whole point of learning the family shape: once you own the different-speed walk, cycle detection is the same tool aimed at a new target. Next you'll aim it once more to find not just whether a loop exists but where it begins (Linked List Cycle II).