← DSA Atlas
Dedicated problem page · #142

Linked List Cycle II

MediumLinked Lists and Pointer ManipulationFloyd cycle detection with entry findingFast and slow pointers (tortoise and hare)
Solve on LeetCode ↗
142
MediumLinked Lists and Pointer ManipulationFast and slow pointers (tortoise and hare)Floyd cycle detection with entry finding

Linked List Cycle II

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null. You must not modify the list, and should aim for O(1) extra memory.

Open official problem prompt ↗
In plain English

Locate the exact node where a cycle starts (or prove none exists) using constant extra memory and without altering the list.

Picture it like this

Two runners on a looping track, one twice as fast; they inevitably meet, and a simple distance argument then walks you back to where the loop joins the straightaway.

Example
Input
head = [3,2,0,-4], pos = 1 (the tail's next points to the node at index 1)
Output
Node with value 2 (the node at index 1)
Why
The tail -4 links back to the node valued 2, so the cycle begins at that node.
Constraints
The number of nodes is in the range [0, 10^4]-10^5 <= Node.val <= 10^5pos is -1 or a valid index into the listpos is not passed as a parameter; it only describes the test structure
Pattern lesson

See the pattern, then code

Floyd cycle detection with entry finding
Recognition clue

Detecting not just whether a cycle exists but where it starts, under an O(1) space constraint, is the signature of Floyd's two-phase algorithm.

↗
Linked Lists and Pointer Manipulation

Reversal, cycle detection, merging, reordering, or O(1)-space sequence edits.. A fast pointer moving twice as fast as a slow one must meet inside any cycle; the distances then satisfy an equation showing that the distance from head to the cycle entry equals the distance from the meeting point to the entry.

New words, made simpleKnow these before the algorithm
Tortoise and hare
Slow pointer (1 step) and fast pointer (2 steps) used to detect and locate cycles.
Cycle entry
The first node that belongs to the loop, where the tail's link points back.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Hash set of visited nodes

Simple and correct but violates the O(1) space goal.

Walk the list storing node references; the first repeat is the entry.

Time O(n)Space O(n)
Best choiceFloyd two-phase

Constant space and does not modify the list.

Detect a meeting point with fast/slow, then reset one pointer to head and advance both by one to find the entry.

Time O(n)Space O(1)
The rule we keep true

Invariant

When the pointers first meet, slow has traveled distance d and fast 2d; letting F be the head-to-entry distance and a the entry-to-meeting distance, the geometry forces F to equal the remaining loop distance from the meeting point back to the entry.

Why this is correct

Reasoning

Fast covers twice slow's distance, so 2(F+a) = F+a+ (loop cycles), giving F = distance from meeting point to entry modulo the loop length; advancing one pointer from head and one from the meeting point at equal speed makes them collide exactly at the entry.

The algorithm in three movesSay these aloud before coding
1Move slow by 1 and fast by 2 until they meet or fast falls off (no cycle)

phase 1: slow & fast meet inside cycle

2If fast or fast.next is None, return None

phase 2: reset ptr to head (3)

3Reset one pointer to head

ptr and slow meet at node index 1 (value 2)

4Advance both pointers one step at a time; they meet at the cycle entry

5Return that meeting node

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
30
21
02
-43
1 · Readslow=fast=head(3)
2 · AskAdvance?
3 · Update stateslow=2, fast=0
4 · ResultNot equal yet.
Key takeaway

The tail -4 loops back to index 1; both pointers converge on that entry node.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-4Launch pointers

    Both start at head; the loop guard fast and fast.next safely handles odd and even lengths and no-cycle lists.

  2. 2
    Lines 5-7Advance and test

    Slow moves one, fast moves two; identity check slow is fast detects the meeting inside a cycle.

  3. 3
    Lines 8-11Find the entry

    Resetting ptr to head and advancing both one step converges on the entry by the distance equality.

  4. 4
    Lines 12No cycle

    If fast reaches the end the loop exits and we return None.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Empty list (head is None)
  • Single node with no cycle
  • Single node pointing to itself
  • Cycle entry is the head itself (F = 0)
!

Common beginner mistakes

  • Comparing values with == instead of node identity with is, which fails on duplicate values
  • Advancing fast without checking fast.next, risking a None dereference
  • Confusing detection (does a cycle exist) with location (where it begins) and stopping after phase 1
Check your understanding

After the pointers meet, why does resetting one to head and moving both by one land on the entry?

More in Linked Lists and Pointer Manipulation

#206Reverse Linked ListIterative pointer reversal#141Linked List CycleFast and slow pointers (Floyd's cycle detection)#143Reorder ListFind middle, reverse second half, merge alternately#138Copy List with Random PointerClone with old-to-new node mapping#146LRU CacheHash map plus recency-ordered structure#2Add Two NumbersDigit-by-digit addition with carry