Linked List Cycle II (LeetCode 142)

Problem

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null. Internally, pos is the index the tail's next points to (-1 means no cycle). Do not modify the list, and use O(1) extra memory.

Example 1

Input: head = [3,2,0,-4], pos = 1

Output: node at index 1

Example 2

Input: head = [1,2], pos = 0

Output: node at index 0

Example 3

Input: head = [1], pos = -1

Output: null (no cycle)

Constraints: 0 ≤ nodes ≤ 10⁴ | −10⁵ ≤ Node.val ≤ 10⁵ | pos is −1 or a valid index

🔗 Linked list

① 🐢🐇 find a meeting point② walk both 1 step → cycle start

🧮 Why phase 2 works

🐢 slow (1 step)🐇 fast (2 steps)💥 meeting point⭐ cycle start a: head → start b: start → meet c: meet → start

Variables

🐢 slow

—

🐇 fast

—

steps

phase

—

💡 Step Logic

Press ▶ Play or Next to begin.

Ready

0 / 0

Pick an example and press Play.

Algorithm

Start 🐢 and 🐇 at head

Move 🐢 1 step and 🐇 2 steps until they meet 💥, or 🐇 hits null (no cycle)

Put 🐢 back at head; keep 🐇 at the meeting point

Move both 1 step at a time until they meet

That node is the cycle start ⭐ — return it

Time

O(n)

Space

O(1)

🧠 The math in one line

When they meet, 🐢 has walked a + b and 🐇 has walked 2(a + b), which is also a + b + k·L (it lapped the loop k times). So a + b = k·L, i.e. a = k·L − b = (k − 1)·L + c. Walking a steps from the meeting point lands on the start. That's exactly what walking a steps from head does.

⚠️ Edge cases

Empty list or one node without a loop → return null. Cycle starts at head (pos = 0) → they meet, and after the reset both are already on the answer. Self-loop at the tail works the same way. A HashSet solution is simpler but uses O(n) memory; interviewers expect this O(1) version.