DSA Where the Cycle Starts

The problem

Detect Cycle Start asks for the first node of the loop inside a linked list. A linked list is a chain of nodes where each node points to the next one. In a list with a loop, the last node points back to an earlier node instead of ending the chain.

The answer is the value of the node where the loop begins, or None when the list has no loop. The cases below are the ones this article tests every solution against.

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

def build(values, cycle_index):
    nodes = [Node(v) for v in values]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    if nodes and cycle_index is not None:
        nodes[-1].next = nodes[cycle_index]
    return (nodes[0] if nodes else None), nodes

cases = [([1, 2, 3, 4, 5], 2, 3), ([10, 20, 30, 40], 0, 10), ([1, 2, 3], None, None)]
for values, cycle_index, expected in cases:
    print("list:", values, "cycle index:", cycle_index, "cycle start:", expected)

The cycle index names a position in the list, counting from zero. In the first case the last node points back to the node at index 2, which holds the value 3. The loop is the run 3, 4, 5, repeated forever.

Intuition: walk and watch for a repeat

The first idea walks the chain and watches the nodes go by. A walk on a loop never ends. The first node the walk visits twice is where the loop begins, because the walk re-enters the loop at exactly that node.

Watching for a repeat means remembering every visited node. The walk below prints its visits, and the repeat stands out at the end of the line.

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

def build(values, cycle_index):
    nodes = [Node(v) for v in values]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    if nodes and cycle_index is not None:
        nodes[-1].next = nodes[cycle_index]
    return (nodes[0] if nodes else None), nodes

head, nodes = build([1, 2, 3, 4, 5], 2)
seen_values = []
node = head
while node is not None and node.value not in seen_values:
    seen_values.append(node.value)
    node = node.next
print("values visited in order:", seen_values)
print("first value visited twice:", node.value if node is not None else None)

The repeat is the answer here, and it rests on node identity, not on values. Two different nodes can hold the same value in a general list. The brute force in the next section therefore remembers the nodes themselves.

Brute force: remember every visited node

The brute force stores each visited node in a list of seen nodes. A node already in the list is the cycle start. A walk that reaches the end of the chain proves there is no loop.

Membership in the list is tested by identity. The counter below records how many nodes the walk had to remember.

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

def build(values, cycle_index):
    nodes = [Node(v) for v in values]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    if nodes and cycle_index is not None:
        nodes[-1].next = nodes[cycle_index]
    return (nodes[0] if nodes else None), nodes

def cycle_start_brute(head):
    seen = []
    node = head
    while node is not None:
        if node in seen:
            return node.value, len(seen)
        seen.append(node)
        node = node.next
    return None, len(seen)

for values, cycle_index in [([1, 2, 3, 4, 5], 2), ([10, 20, 30, 40], 0), ([1, 2, 3], None)]:
    head, nodes = build(values, cycle_index)
    start, stored = cycle_start_brute(head)
    print("list:", values, "cycle start:", start, "nodes remembered:", stored)

The memory grows with the list. A million-node list makes the walk remember up to a million nodes to answer one question. The optimal solution remembers nothing at all.

The optimal solution: two pointers, then one restart

A slow pointer moves one step at a time and a fast pointer moves two, and when the list has a loop the fast pointer laps the slow one until they meet inside the loop. That meeting proves the loop, and restarting one pointer at the head while both then move one step at a time makes them meet again exactly at the cycle start.

The method is often called Floyd's algorithm. Its second phase works because the distance from the head to the cycle start equals the distance from the meeting point to the cycle start, measured along the chain.

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

def build(values, cycle_index):
    nodes = [Node(v) for v in values]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    if nodes and cycle_index is not None:
        nodes[-1].next = nodes[cycle_index]
    return (nodes[0] if nodes else None), nodes

def cycle_start(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:
            break
    else:
        return None
    slow = head
    while slow is not fast:
        slow = slow.next
        fast = fast.next
    return slow.value

cases = [([1, 2, 3, 4, 5], 2, 3), ([10, 20, 30, 40], 0, 10), ([1, 2, 3], None, None)]
for values, cycle_index, expected in cases:
    head, nodes = build(values, cycle_index)
    result = cycle_start(head)
    print("list:", values, "->", result, "expected:", expected, "match:", result == expected)

All three cases from the start of the article pass. The loop's while-else deserves one look. The else runs only when the fast pointer runs off the end, which is exactly the no-loop case.

Walkthrough: [1, 2, 3, 4, 5] looping back to 3

The walk runs both phases on the first case. Phase one prints both pointers after each round of moves. Phase two restarts one pointer at the head and prints each single step.

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

def build(values, cycle_index):
    nodes = [Node(v) for v in values]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    if nodes and cycle_index is not None:
        nodes[-1].next = nodes[cycle_index]
    return (nodes[0] if nodes else None), nodes

head, nodes = build([1, 2, 3, 4, 5], 2)
slow = head
fast = head
step = 0
while True:
    slow = slow.next
    fast = fast.next.next
    step += 1
    print("phase one step", step, "- slow:", slow.value, "fast:", fast.value)
    if slow is fast:
        print("met at:", slow.value)
        break
slow = head
steps = 0
while slow is not fast:
    print("phase two - head pointer:", slow.value, "meeting pointer:", fast.value)
    slow = slow.next
    fast = fast.next
    steps += 1
print("phase two steps:", steps, "cycle start:", slow.value)

Phase one meets at the node holding 4, which is inside the loop but not its start. Phase two takes two paired steps and lands both pointers on 3. The meeting point alone never answers the question, and treating it as the answer is the classic error.

Complexity

Both methods walk the chain a bounded number of times, so both take O(n) time for n nodes. They differ in space, and space is the whole point of the upgrade.

The brute force stores up to n nodes, so its space is O(n). The two-pointer method stores two node references, so its space is O(1).

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

def build(values, cycle_index):
    nodes = [Node(v) for v in values]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    if nodes and cycle_index is not None:
        nodes[-1].next = nodes[cycle_index]
    return (nodes[0] if nodes else None), nodes

def brute_count(head):
    seen = []
    node = head
    while node is not None:
        if node in seen:
            return len(seen)
        seen.append(node)
        node = node.next
    return len(seen)

def floyd_steps(head):
    slow = head
    fast = head
    steps = 0
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        steps += 1
        if slow is fast:
            break
    return steps

for n in [5, 10, 20]:
    values = list(range(1, n + 1))
    head, nodes = build(values, n // 2)
    print("nodes:", n, "brute nodes stored:", brute_count(head), "floyd phase one steps:", floyd_steps(head), "floyd nodes stored: 0")

The stored count tracks the list size exactly. The pointer method's memory stays flat while its step count grows at the same rate as the walk itself. Time is traded for nothing here; only memory improves.

Edge cases and pitfalls

A single node that points to itself is the smallest loop. Its cycle start is itself. A single node pointing nowhere has no loop, and the two cases differ by one link only.

Comparing values instead of nodes is the quiet bug in this problem. The brute force above stores nodes and tests identity, so two nodes holding equal values never confuse it. A version that stores values can report a start where no loop exists.

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

def build(values, cycle_index):
    nodes = [Node(v) for v in values]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    if nodes and cycle_index is not None:
        nodes[-1].next = nodes[cycle_index]
    return (nodes[0] if nodes else None), nodes

def cycle_start(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:
            break
    else:
        return None
    slow = head
    while slow is not fast:
        slow = slow.next
        fast = fast.next
    return slow.value

head, nodes = build([], None)
print("empty list:", cycle_start(head))
head, nodes = build([1], 0)
print("one node, points to itself:", cycle_start(head))
head, nodes = build([1], None)
print("one node, no loop:", cycle_start(head))
head, nodes = build([1, 2], 0)
print("two nodes, loop at head:", cycle_start(head))
head, nodes = build([7, 7, 7], None)
print("repeated values, no loop:", cycle_start(head))
head, nodes = build([1, 2, 3, 4], 3)
print("loop of one node at the tail:", cycle_start(head))

The repeated-values row returns None, as it must. The loop is a fact about links, not about the values the nodes carry. Every check in the optimal code follows links and identities, never values.