Detect whether a linked list has a cycle using Floyd's fast/slow pointer algorithm.

How to think about it

When an interviewer hands you a linked list and asks “does it loop back on itself?”, the easy answer is a hash set of every node you’ve walked past — see a node twice, you have a cycle. It works, and it’s O(n) time, but it costs O(n) space, and the moment you say it the interviewer will lean in and ask you to do it without the set. What they’re really probing is whether you know Floyd’s fast/slow pointers — the trick that detects the loop with two pointers and nothing else.

The idea is a race on a track. Put two runners at the start: slow takes one step at a time, fast takes two. If the track is a straight line — no cycle — the fast runner simply runs off the end and you see None. If the track bends back into a loop, the fast runner keeps lapping the circle and eventually catches the slow one from behind. They must meet, because each step the gap between them shrinks by exactly one. So the whole algorithm is: step both, and the instant slow is fast, you have your cycle.

A worked example

class Node:
    def __init__(self, val, nxt=None):
        self.val = val
        self.next = nxt

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:            # same object in memory — a cycle
            return True
    return False                    # fast fell off the end — no cycle

# Build a cyclic list: 1 -> 2 -> 3 -> 4 -> 2 (back to node 2)
n1, n2, n3, n4 = Node(1), Node(2), Node(3), Node(4)
n1.next = n2; n2.next = n3; n3.next = n4; n4.next = n2   # the loop

print(has_cycle(n1))        # cyclic list
print(has_cycle(Node(1, Node(2, Node(3)))))  # 1 -> 2 -> 3 -> None
print(has_cycle(Node(7)))   # single node, no cycle
print(has_cycle(None))      # empty list

True
False
False
False

The first list bends 4 back to 2, so fast wraps around the loop, closes the gap on slow, and they collide — True. The other three are straight lines (or empty), so fast reaches None and the loop in has_cycle exits with False. Notice that the while fast and fast.next guard is what lets fast.next.next be safe: you check both the node and its successor exist before taking the double step.