Practice: Measuring the Loop in a Treasure Trail

Each clue names the place of the next: does the trail loop, where does the loop begin, and how many places does it hold?

Measuring a loop uses both phases of fast and slow pointers and then one lap. A treasure trail is stored as a linked list of places, each clue naming the next: the well, the oak, the bridge, the mill, the chapel, and the chapel's clue leads back to the bridge. Using O(1) extra memory, decide whether the trail loops, find the place where the loop begins, and count the places in the loop.

Show the answer and a solution

The trail loops: slow and fast meet at the mill. The loop begins at the bridge and holds 3 places, the bridge, the mill and the chapel. The first phase finds the meeting.

Phase 1: slow and fast on the trail

Inputwell → oak → bridge → mill → chapel → bridge

Start: both on well
1. wellslowfast
2. oak
3. bridge
4. mill
5. chapel
Both start at the well
Move 1: slow oak, fast bridge
1. well
2. oakslow
3. bridgefast
4. mill
5. chapel
Slow at the oak, fast at the bridge
Move 2: slow bridge, fast chapel
1. well
2. oak
3. bridgeslow
4. mill
5. chapelfast
Slow at the bridge, fast at the chapel
Move 3: slow mill, fast mill
1. well
2. oak
3. bridge
4. millslowfast
5. chapel
Fast goes from the chapel back through the bridge to the mill, where slow has just arrived

ResultThey meet at the mill, so the trail loops.

The second phase sends slow back to the well and moves both one place at a time.

Phase 2: from the well and from the mill, one place a move

Inputwell → oak → bridge → mill → chapel → bridge

Phase 2: slow back on well, fast on mill
1. wellslow
2. oak
3. bridge
4. millfast
5. chapel
Slow restarts at the well, fast stays at the mill
Step 1: slow oak, fast chapel
1. well
2. oakslow
3. bridge
4. mill
5. chapelfast
Slow at the oak, fast at the chapel
Step 2: slow bridge, fast bridge
1. well
2. oak
3. bridgeslowfast
4. mill
5. chapel
Both reach the bridge

ResultThe loop begins at the bridge.

Counting the loop is one lap from the meeting point: from the mill to the chapel, the bridge and back to the mill is 3 moves. The tail is a = 2 places and the meeting is b = 1 place into the loop, so a + b = 3 is exactly one lap of L = 3. The listing runs all three steps.

treasure_trail.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 loop_start(head, meeting):
    slow, fast = head, meeting
    while slow is not fast:
        slow = slow.next
        fast = fast.next
    return slow


def loop_length(meeting):
    length = 1
    node = meeting.next
    while node is not meeting:
        node = node.next
        length += 1
    return length


head = build(["well", "oak", "bridge", "mill", "chapel"], 2)
meeting = meeting_node(head)
print("pointers meet at:", meeting.val)
print("loop starts at:", loop_start(head, meeting).val)
print("places in the loop:", loop_length(meeting))

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

pointers meet at: mill
loop starts at: bridge
places in the loop: 3

Each step is O(n) time for n places and the whole solution keeps three references, O(1) extra space. A set of visited places would answer the first two questions in one walk, at the cost of memory for every place.

← → move through sections and cards