141. Linked List Cycle

141

EasyLinked Lists and Pointer ManipulationTwo pointers moving at different speedsFast and slow pointers (Floyd's cycle detection)

Linked List Cycle

Given the head of a linked list, determine whether the list contains a cycle — that is, whether some node's next pointer eventually revisits an earlier node. Return true if a cycle exists, otherwise false.

Open official problem prompt ↗

In plain English

Report whether following next pointers ever loops, without recording every visited node.

Picture it like this

Two runners on a track: if the track is a loop, the faster runner eventually laps and meets the slower one; on a straight track the fast runner just finishes and there is no meeting.

Example

Input: head = [3, 2, 0, -4] with the tail's next connected to index 1
Output: true
Why: Following next from -4 returns to node 2, so the traversal loops forever — a cycle exists.

Constraints

The number of nodes is in the range [0, 10^4]-10^5 <= Node.val <= 10^5pos is -1 (no cycle) or a valid index into the list

Pattern lesson

See the pattern, then code

Fast and slow pointers (Floyd's cycle detection)

↗

Linked Lists and Pointer Manipulation

Reversal, cycle detection, merging, reordering, or O(1)-space sequence edits.. If a cycle exists, a pointer moving two steps will lap a pointer moving one step and land on the same node; if there is no cycle, the fast pointer simply runs off the end.

New words, made simpleKnow these before the algorithm

Cycle: A next pointer that leads back to a previously visited node, creating an endless loop.
Tortoise and hare: Two pointers advancing at speeds one and two.
Identity check: Comparing nodes with 'is' to test they are the same object, not equal values.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Hash set of visited nodes

Correct but uses linear extra memory.

Store each node; if you see one twice there is a cycle.

Time O(n)Space O(n)

Best choiceFloyd's two-pointer detection

Constant memory, single pass — the intended solution.

Move slow by one and fast by two; a collision proves a cycle.

Time O(n)Space O(1)

The rule we keep true

Invariant

As long as both pointers stay inside the list, fast is always an even number of steps ahead of slow (modulo the cycle length once both are inside a loop).

Why this is correct

Reasoning

Once both pointers are inside a cycle of length L, the gap between them shrinks by exactly one each step, so within at most L steps it reaches zero and they collide; if there is no cycle, fast hits None first.

The algorithm in three movesSay these aloud before coding

1Start slow and fast at the head

slow=3, fast=3

2Advance slow by one and fast by two each iteration

slow=2, fast=0

3If fast reaches None or fast.next is None, there is no cycle

slow=0, fast=2

4If slow and fast ever reference the same node, return true

slow=-4, fast=-4 -> True

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

-43

1 · Readhead=3

2 · AskBoth at start?

3 · Update stateslow=3, fast=3

4 · Resultenter loop since fast and fast.next exist

Key takeaway

The tail (-4) links back to node 2, so the fast pointer eventually collides with the slow pointer inside the loop.

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
Lines 3Anchor both pointers
slow and fast both start at the head.
2
Lines 4-8Move and compare
Guard fast and fast.next so two hops are safe, then check for a collision after moving.
3
Lines 9No cycle
Falling out of the loop means fast reached the end, so the list is acyclic.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Empty list returns false immediately
Single node with next=None returns false
Single node pointing to itself returns true
Two nodes forming a loop

Common beginner mistakes

Checking slow == fast with value equality instead of identity (is)
Not guarding fast.next before fast.next.next, causing a None dereference
Starting the pointers at different nodes and misreporting a false collision

Check your understanding

Why is it enough to guard both fast and fast.next in the while condition?

Linked List Cycle

Linked List Cycle

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Linked Lists and Pointer Manipulation