Taking the Meeting Point as the Start of the Cycle

The pointers meet somewhere inside the cycle, usually not at its first node, and only the second phase finds that node.

The node where slow and fast meet is inside the cycle but is usually not its first node, so returning it as the start of the cycle gives a wrong answer that looks plausible. The meeting point depends on how far fast has to catch up, which depends on the length of the tail before the cycle, and it lands on the first node only by coincidence. On 8 3 6 1 9 4 7, with 7 linking back to 1, the cycle starts at 1 and the pointers meet on 9.

Returning the meeting node against running the second phase

meeting_point.pypy

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


def build(values, cycle_start):
    nodes = [ListNode(val) for val in values]
    for node, following in zip(nodes, nodes[1:]):
        node.next = following
    nodes[-1].next = nodes[cycle_start]
    return nodes[0]


def meeting_node(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return slow
    return None


head = build([8, 3, 6, 1, 9, 4, 7], 3)
print("returned as the start:", meeting_node(head).val)

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

returned as the start: 9

cycle_start.pypy

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


def build(values, cycle_start):
    nodes = [ListNode(val) for val in values]
    for node, following in zip(nodes, nodes[1:]):
        node.next = following
    nodes[-1].next = nodes[cycle_start]
    return nodes[0]


def meeting_node(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return slow
    return None


def cycle_start(head):
    meeting = meeting_node(head)
    if meeting is None:
        return None
    slow, fast = head, meeting
    while slow is not fast:
        slow = slow.next
        fast = fast.next
    return slow


head = build([8, 3, 6, 1, 9, 4, 7], 3)
print("meeting node:", meeting_node(head).val)
print("returned as the start:", cycle_start(head).val)

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

meeting node: 9
returned as the start: 1

The first listing reports 9, and the second walks on from the meeting and reports 1. The trace shows both phases.

Both phases on 8 3 6 1 9 4 7, with 7 linking back to 1

Input8 → 3 → 6 → 1 → 9 → 4 → 7 → 1

Start: both on 8
1. 8slowfast
2. 3
3. 6
4. 1
5. 9
6. 4
7. 7
Both start on 8
Move 1: slow 3, fast 6
1. 8
2. 3slow
3. 6fast
4. 1
5. 9
6. 4
7. 7
Slow on 3, fast on 6
Move 2: slow 6, fast 9
1. 8
2. 3
3. 6slow
4. 1
5. 9fast
6. 4
7. 7
Fast is inside the cycle on 9
Move 3: slow 1, fast 7
1. 8
2. 3
3. 6
4. 1slow
5. 9
6. 4
7. 7fast
Fast passes 4 and lands on 7
Move 4: slow 9, fast 9
1. 8
2. 3
3. 6
4. 1
5. 9slowfast
6. 4
7. 7
Fast goes from 7 back through 1 to 9 and meets slow there
Phase 2: slow back on 8, fast on 9
1. 8slow
2. 3
3. 6
4. 1
5. 9fast
6. 4
7. 7
Phase 2: slow restarts at 8, fast stays on 9
Step 1: slow 3, fast 4
1. 8
2. 3slow
3. 6
4. 1
5. 9
6. 4fast
7. 7
Each moves one node
Step 2: slow 6, fast 7
1. 8
2. 3
3. 6slow
4. 1
5. 9
6. 4
7. 7fast
Slow reaches 6 as fast reaches the last node, 7
Step 3: slow 1, fast 1
1. 8
2. 3
3. 6
4. 1slowfast
5. 9
6. 4
7. 7
Both reach 1, the first node of the cycle

ResultThe pointers met on 9; the cycle starts at 1.

The tail here is a = 3 nodes, 8 3 6, and the cycle 1 9 4 7 holds 4, so the meeting is b = 1 node into the cycle, where a + b fills one lap. The fix is the second phase: one pointer back to the head, both moving one node a move, and the node where they meet is the start. The mistake survives a test on a list whose cycle starts at the head, or one where the meeting falls on the start by chance, as it does for the codes 3 10 2 5 4 6 with 6 leading back to 4; it shows on any list where the meeting falls past the first node of the cycle, which is most lists with a tail.

← → move through sections and cards