DSA Detecting a Cycle (Floyd's)

The problem

A cycle is a loop inside a linked list. One node's next link points back to an earlier node. A walk on such a list never reaches None.

The problem gives the head of a list. The answer is True when the list holds a cycle. The answer is False when the walk ends at None.

The cases name the link that closes each loop. A position of -1 means no link back. Any other position is the index of the node the tail links to.

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


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


def build_cycle(values, pos):
    head = build(values)
    if head is None or pos < 0:
        return head
    target = head
    for _ in range(pos):
        target = target.next
    tail = head
    while tail.next is not None:
        tail = tail.next
    tail.next = target
    return head


cases = [
    ([1, 2, 3, 4], -1, False),
    ([1, 2, 3, 4], 1, True),
    ([1, 2, 3], 0, True),
    ([1], 0, True),
    ([1], -1, False),
]
for values, pos, expected in cases:
    print("values", values, "tail links to index", pos, "has cycle:", expected)
print("plain list:", render(build([1, 2, 3, 4])))

Read the second row closely. The tail holds 4 and links back to index 1, the node holding 2. The walk then repeats 2, 3, 4 forever.

A cyclic list cannot be printed as a chain. Its render would loop forever. The cases therefore print the values and the closing link, not a rendered chain.

Intuition

The first idea is to follow next links and wait for None. That walk works on a plain list. On a cyclic list it never ends.

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


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


def build_cycle(values, pos):
    head = build(values)
    if head is None or pos < 0:
        return head
    target = head
    for _ in range(pos):
        target = target.next
    tail = head
    while tail.next is not None:
        tail = tail.next
    tail.next = target
    return head


head = build_cycle([1, 2, 3, 4], 1)
node = head
seen_values = []
for _ in range(10):
    seen_values.append(node.value)
    node = node.next
print("ten steps of values:", seen_values)
print("reached None:", node is None)

The values repeat from the second node onward. Ten steps never reach None. A detector needs a stopping rule beyond reaching the end.

Remembering visited nodes gives that rule. A set of visited nodes spots the first repeat. A repeat can only happen when the walk loops back.

Changing the nodes is a trap. Marking a node by editing its value corrupts data the caller owns. It also breaks when two nodes share a value. The set keeps its marks outside the list.

Brute force

The brute force stores every visited node in a set. It stores the node itself, by identity. Equal values in different nodes stay distinct that way.

The walk stops in two ways. It reaches None, so there is no cycle. Or it meets a stored node, so there is one.

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


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


def build_cycle(values, pos):
    head = build(values)
    if head is None or pos < 0:
        return head
    target = head
    for _ in range(pos):
        target = target.next
    tail = head
    while tail.next is not None:
        tail = tail.next
    tail.next = target
    return head


def has_cycle_set(head):
    seen = set()
    node = head
    visits = 0
    while node is not None:
        visits += 1
        if id(node) in seen:
            return True, visits
        seen.add(id(node))
        node = node.next
    return False, visits

cases = [
    ([1, 2, 3, 4], -1),
    ([1, 2, 3, 4], 1),
    ([1, 2, 3], 0),
    ([1], 0),
    ([1], -1),
]
for values, pos in cases:
    result, visits = has_cycle_set(build_cycle(values, pos))
    print("values", values, "pos", pos, "cycle:", result, "visits:", visits)

Every case from the start of the article passes. The cyclic four-node case detects the repeat on its fifth visit. The walk meets the node holding 2 a second time there.

The cost is memory. The set grows by one entry per node. A long plain list fills the set completely before the walk can finish.

The optimal solution: the tortoise and the hare

Walk two pointers at two speeds, because inside any loop the faster pointer gains one node per round and must land on the slower one. That gain is the key idea.

The slow pointer is the tortoise. It moves one node per round. The fast pointer is the hare. It moves two nodes per round.

Two outcomes are possible. The hare reaches None, so the list is plain. Or the two pointers land on the same node, so the list loops.

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


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


def build_cycle(values, pos):
    head = build(values)
    if head is None or pos < 0:
        return head
    target = head
    for _ in range(pos):
        target = target.next
    tail = head
    while tail.next is not None:
        tail = tail.next
    tail.next = target
    return head


def has_cycle(head):
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

cases = [
    ([1, 2, 3, 4], -1),
    ([1, 2, 3, 4], 1),
    ([1, 2, 3], 0),
    ([1], 0),
    ([1], -1),
]
for values, pos in cases:
    print("values", values, "pos", pos, "cycle:", has_cycle(build_cycle(values, pos)))

All five cases pass. The comparison uses is, not value equality. Two distinct nodes can hold the same value, and only landing on the very same node proves a loop.

No set is built. The list is left untouched. The meeting node sits inside the loop, but it is not always the node where the loop starts.

Walkthrough

Watch the two pointers on the list 1, 2, 3, 4 with the tail linked to 2. The printout shows both values after each round.

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


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


def build_cycle(values, pos):
    head = build(values)
    if head is None or pos < 0:
        return head
    target = head
    for _ in range(pos):
        target = target.next
    tail = head
    while tail.next is not None:
        tail = tail.next
    tail.next = target
    return head


head = build_cycle([1, 2, 3, 4], 1)
slow = head
fast = head
print("start: slow", slow.value, "fast", fast.value)
round_no = 0
while fast is not None and fast.next is not None:
    slow = slow.next
    fast = fast.next.next
    round_no += 1
    print("round", round_no, ": slow", slow.value, "fast", fast.value)
    if slow is fast:
        print("met at value:", slow.value)
        break

Round one puts slow on 2 and fast on 3. Round two puts slow on 3 and fast back on 2. The hare has entered the loop and wrapped around.

Round three lands both pointers on 4. The meeting proves the cycle. It says nothing about where the loop starts.

Complexity

The time cost is O(n) for a list of n nodes. On a plain list the hare reaches the end in half-length rounds. On a cyclic list the hare gains one node per round inside the loop.

The space cost is O(1). Two pointers are stored. The set detector, by contrast, stores one entry per visited node.

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


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


def build_cycle(values, pos):
    head = build(values)
    if head is None or pos < 0:
        return head
    target = head
    for _ in range(pos):
        target = target.next
    tail = head
    while tail.next is not None:
        tail = tail.next
    tail.next = target
    return head


def set_detector_cost(head):
    seen = set()
    node = head
    steps = 0
    while node is not None:
        seen.add(id(node))
        steps += 1
        node = node.next
    return steps, len(seen)

def floyd_rounds(head):
    slow = head
    fast = head
    rounds = 0
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        rounds += 1
    return rounds

for size in [8, 16, 32]:
    head = build(list(range(1, size + 1)))
    steps, stored = set_detector_cost(head)
    print("nodes", size, "set steps:", steps, "set entries:", stored, "floyd rounds:", floyd_rounds(head))

The set entries double when the list doubles. The count reaches the full length every time. Floyd rounds also grow in a straight line, but the stored entries stay at zero.

Edge cases and pitfalls

An empty list has no cycle. A single node without a link back has no cycle either. Both walks reach None at once.

A single node can still loop. Its next link can point at itself. A cycle at the head is the other sharp case, where every node sits inside the loop.

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


def build(values):
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


def render(head):
    parts = []
    node = head
    while node is not None:
        parts.append(str(node.value))
        node = node.next
    parts.append("None")
    return " -> ".join(parts)


def build_cycle(values, pos):
    head = build(values)
    if head is None or pos < 0:
        return head
    target = head
    for _ in range(pos):
        target = target.next
    tail = head
    while tail.next is not None:
        tail = tail.next
    tail.next = target
    return head


def has_cycle(head):
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

print("empty:", has_cycle(None))
print("single, no loop:", has_cycle(build_cycle([1], -1)))
print("single, self loop:", has_cycle(build_cycle([1], 0)))
print("cycle at head:", has_cycle(build_cycle([1, 2, 3], 0)))
print("two nodes, loop:", has_cycle(build_cycle([1, 2], 0)))
print("two nodes, plain:", has_cycle(build_cycle([1, 2], -1)))

Comparing values is the classic pitfall. A plain list can hold the value 2 twice in two nodes. Value equality would report a cycle that is not there.

Assuming the meeting node starts the loop is the second pitfall. The walkthrough met at 4. The loop there starts at 2.