How do you solve Linked List Cycle II?

Use two pointers, slow and fast, starting at head. Move slow by one step and fast by two steps until they meet or fast reaches the end (no cycle). If they meet, reset slow to head and move both pointers one step at a time until they meet again; this node is the cycle start. Return this node. If no cycle, return null.

Linked List Cycle II

Q: What is the time complexity of Linked List Cycle II?

O(n). Each pointer traverses the list at most a constant number of times. The fast pointer moves twice as fast, so the detection phase is O(n), and the entry point search is also O(n).

Q: What pattern does Linked List Cycle II use?

The Pattern: Fast & Slow Pointers (Cycle Detection and Entry Point Identification) The Heuristic: When detecting cycles in linked structures, use two pointers moving at different speeds to find a meeting point inside the cycle; then reset one pointer to the start and move both at equal speed to find the cycle's entry point.

Medium Fast & Slow Pointers

Problem

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

The number of nodes in the list is in the range [0, 10⁴]
−10⁵ ≤ Node.val ≤ 10⁵
pos is −1 or a valid index in the linked-list

Example

Input: head = [3,2,0,-4], where the tail connects to the node at position 1 (0-indexed)

Output: Reference to the node with value 2

The algorithm uses two pointers moving at different speeds to detect a cycle. Initially, both pointers start at the head. The fast pointer moves two steps at a time, while the slow pointer moves one step. If a cycle exists, the two pointers will eventually meet inside the cycle. Once they meet, resetting one pointer to the head and moving both one step at a time leads them to meet again at the cycle's start node. This works because the distance from the head to the cycle start equals the distance from the meeting point to the cycle start along the cycle.

Approach

Straightforward Solution

A brute-force approach uses a hash set to track visited nodes, returning the first repeated node. This requires O(n) extra space and is less optimal.

Core Observation

If a cycle exists, two pointers moving at different speeds will eventually meet inside the cycle due to the relative speed difference.

Path to Optimal

Preview

The key insight is Floyd's Tortoise and Hare algorithm: use two pointers moving at different speeds to detect a cycle without extra space…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use two pointers, slow and fast, starting at head. Move slow by one step and fast by two steps until they meet or fast reaches the end (no cycle)…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each pointer traverses the list at most a constant number of times. The fast pointer moves twice as fast, so the detection phase is O(n), and the entry point search is also O(n).

Space

O(1)

Only two pointers are used, with no additional data structures, resulting in constant auxiliary space.

Pattern Spotlight

Fast & Slow Pointers (Cycle Detection and Entry Point Identification)

When detecting cycles in linked structures, use two pointers moving at different speeds to find a meeting point inside the cycle; then reset one pointer to the start and move both at equal speed to find the cycle's entry point.

Solution

Python

1class Solution:
2    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
3
4        slow = head
5        fast = head
6
7        while fast and fast.next:
8
9            slow = slow.next
10            fast = fast.next.next
11
12            if slow == fast:
13                slow = head
14
15                while slow != fast:
16                    slow = slow.next
17                    fast = fast.next
18
19                return slow
20
21        return None

Step-by-Step Solution

Initialize Slow and Fast Pointers at Head

4slow = head
5fast = head

Objective

To set up two pointers that will traverse the linked list at different speeds to detect a cycle.

Key Insight

Starting both pointers at the head ensures they begin traversal from the same position. The fast pointer moves twice as fast as the slow pointer, which guarantees that if a cycle exists, they will eventually meet inside the cycle. This setup is the foundation of Floyd's cycle detection algorithm.

Interview Quick-Check

Core Logic

Both pointers start at the head to ensure synchronized traversal and correct detection of cycles.

Common Pitfalls & Bugs

Initializing pointers incorrectly (e.g., fast starting at head.next) can cause missed cycles or incorrect detection.

Traverse List to Detect Cycle via Pointer Meeting

To move the slow pointer by one step and the fast pointer by two steps until they meet or the list ends.

Identify Cycle Start by Resetting Slow and Moving Both Pointers

To find the node where the cycle begins by resetting slow to head and moving both pointers one step at a time until they meet.

Return the Node Where Cycle Begins or Null if None

To return the node where the cycle starts if found, or null if no cycle exists.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 5 Critical lines interviewers watch for.

Line 12 Critical

if slow == fast:

Check if slow and fast pointers have met.

Meeting of slow and fast pointers confirms the presence of a cycle, triggering the next phase to find the cycle's start.

Line 10 Critical

fast = fast.next.next

Move fast pointer two steps forward.

Moving fast two steps ahead ensures it will eventually catch up to slow if a cycle exists, enabling detection without extra space.

Line 13 Critical

slow = head

Reset slow pointer to the head of the list.

Resetting slow to head prepares for the second phase where both pointers move at the same speed to find the cycle entry point, leveraging the distance equality property.

Full line-by-line criticality + rationale for all 12 lines available on Pro.

Test Your Understanding

Why does resetting one pointer to the head and moving both pointers at the same speed lead to the cycle's start node?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Linked List Cycle II from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Linked List Cycle II drill

or drill a free problem

1	`class Solution:`
2	`def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:`
3
4	`slow = head`
5	`fast = head`
6
7	`while fast and fast.next:`
8
9	`slow = slow.next`
10	`fast = fast.next.next`
11
12	`if slow == fast:`
13	`slow = head`
14
15	`while slow != fast:`
16	`slow = slow.next`
17	`fast = fast.next`
18
19	`return slow`
20
21	`return None`