Build a Linked ListStep 3 of 5

Detect a Cycle

12345

Step 3: Detect a Cycle

A well-formed list ends at None, but a broken one can loop back on itself. Floyd's tortoise and hare algorithm detects this with two pointers moving at different speeds.

Implement has_cycle(head) that returns True if the list contains a cycle and False otherwise. Move a slow pointer one step and a fast pointer two steps each iteration. If they ever land on the same node, there is a cycle. If fast reaches None, there is not.

The tests build a normal list, then create a cycle by pointing the tail's next back at an earlier node.

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


def from_list(values):
    head = None
    for v in reversed(values):
        head = Node(v, head)
    return head


def to_list(head):
    out = []
    node = head
    while node is not None:
        out.append(node.value)
        node = node.next
    return out


def reverse(head):
    prev = None
    cur = head
    while cur is not None:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    return prev


def has_cycle(head):
    """Return True if the list contains a cycle, else False."""
    # TODO: advance slow by one and fast by two; a meeting means a cycle
    pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousNext step