cconnected.
Understand the pattern. Find your own way.Find your starting point
Your learning feed/Idea 40 of 218
Ideas this builds on
Linked lists40 / 218

Linked List Cycle

Picture

Slow moves one edge; fast moves two. On an acyclic chain, fast reaches the end first.

Predict

Does the first slow-fast meeting always equal the cycle entrance?

Walk through the small example

No. Different speeds guarantee a meeting in a finite cycle; equal-speed phase two locates its entrance.

Mental model and complete Python solution

Fast’s extra distance at the meeting is a whole number of cycle lengths. That congruence makes distance from head to entrance match the remaining cycle distance from meeting.

What the function promises: Return the entrance node of a stable singly linked list cycle, or None.

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

def build(values):
    head = None
    for value in reversed(values):
        head = Node(value, head)
    return head

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

def cycle_entrance(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            seeker = head
            while seeker is not slow:
                seeker, slow = seeker.next, slow.next
            return seeker
    return None

a, b, c = Node(1), Node(2), Node(3)
a.next, b.next, c.next = b, c, b
assert cycle_entrance(a) is b
assert cycle_entrance(build([1,2])) is None

Work and storage: O(n) time and O(1) extra space.

When to recognize it: Different speeds guarantee a meeting in a finite cycle; equal-speed phase two locates its entrance.

Check before applying it: The arithmetic assumes deterministic next references that do not change during traversal.

Change one rule

Need the cycle length too.

See what changes

After the meeting, walk once around the cycle while counting edges.

Connect

Linked lists: follow references: The graph has outdegree at most one.

components coloring: General graph cycles need broader visited-state reasoning.