Linked List Cycle

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next          # tortoise: 1 step
        fast = fast.next.next     # hare: 2 steps
        if slow is fast:
            return True           # they met
    return False                  # hare hit the end

Linked List Cycle. Given the head of a linked list, does it ever loop back on itself?

Here are six nodes. The last one points back to node three, so a walk along the arrows goes round forever.

The simple way: remember every node you visit in a set. Reach one that's already there, and you've found a cycle. It works, but the set needs memory for every node.

Floyd's trick uses two runners. The tortoise moves one step at a time. The hare moves two. If the list ends, the hare falls off first. If there's a loop, the hare gains one step every turn, so it must land on the tortoise.

In code, start both at the head. While the hare can jump, move the tortoise once and the hare twice. If they're on the same node, return true. If the loop ends, return false.

Let's race. Step one: tortoise on two, hare on three. Step two: tortoise on three, hare on five. Step three: the hare wraps around to three, the tortoise reaches four. Step four: both land on five. They meet: a cycle.

Now cut the link back. The hare jumps to three, then five, then off the end. No cycle.

The hare catches up within one lap, so the time is O of n. Just two pointers, so the space is O of one.

One slow, one fast, no memory. That's Linked List Cycle.