Introduction

The Detect Cycle II problem involves finding the starting node of a cycle in a linked list.

The task is to:

  • detect whether cycle exists
  • identify the node where cycle begins
  • use optimized pointer traversal

Example:

Input:1 -> 2 -> 3 -> 4
     ↑       ↓
      ← ← ← ←

Output:
2

Explanation:

Node 4 points back to node 2.
Cycle starts at:
2

This problem is one of the most important applications of:

Fast and Slow Pointer Technique

Constraints

1 <= Number of Nodes <= 10^5
-10^9 <= Node Value <= 10^9

Approach 1 : Brute Force (Using HashSet)

Explanations:

Explanation:

The idea is:

  • traverse linked list
  • store visited nodes
  • first repeated node
    is cycle start

Steps:

  1. Traverse linked list.
  2. Store visited nodes.
  3. If node repeats:
    return node.

This approach works but:

  • uses extra memory

So Floyd’s Cycle Detection solution is preferred.

Dry Run

Input:1 -> 2 -> 3 -> 4
     ↑       ↓
      ← ← ← ←

Visit:
1

Store:
{1}

Visit:
2

Store:
{1,2}

Visit:
3

Store:
{1,2,3}

Visit:
4

Next:
2 already exists

Cycle starts at:
2

Practice :

Complexity Analysis :

Time Complexity:- O(n)Explanation :
Each node is visited once.

Space Complexity:- O(n)
Explanation :
HashSet stores visited nodes.

Approach 2 : Optimal Solution(Using Floyd’s Algorithm)

Explanations:

Explanation:

This is the most optimized and interview-preferred solution.

The idea is:

  • use slow and fast pointers
  • detect cycle first
  • move one pointer to head
  • move both one step

The meeting point becomes:

  • cycle starting node

Dry Run

Input:1 -> 2 -> 3 -> 4
     ↑       ↓
      ← ← ← ←

Step 1:
Slow and fast meet

Step 2:
Move slow to head

Step 3:
Move both one step

Both meet at:
2

Cycle starts at:
2

Practice :

Complexity Analysis :

Time Complexity:- O(n)
Explanation :
Pointers traverse linked list efficiently.

Space Complexity:- O(1)
Explanation :
No extra space is used.

Why This Problem is Important

This problem builds the foundation for:

  • Floyd’s Algorithm
  • Cycle detection
  • Fast & Slow Pointer
  • Pointer optimization
  • Linked List traversal

Real-World Applications

Cycle detection concepts are used in:

  • Deadlock detection
  • Network routing
  • Operating systems
  • Graph traversal
  • Memory management

Common Beginner Mistakes

  • Incorrect fast pointer updates
  • Forgetting cycle detection phase
  • Wrong pointer reset logic
  • Infinite loops
  • NULL pointer errors

Interview Tip

Interviewers often expect:

  • Floyd’s Algorithm explanation
  • O(1) space optimization
  • proper pointer traversal
  • cycle start detection logic

Always explain:

  • why resetting one pointer works
  • how both pointers meet at cycle start

Related Questions

  • Linked List Cycle
  • Happy Number
  • Middle of Linked List
  • Reverse Linked List
  • Floyd Cycle Detection

Final Takeaway

The Detect Cycle II problem is one of the most important Fast & Slow Pointer problems.

It teaches:

  • Floyd’s Algorithm
  • cycle start detection
  • pointer optimization
  • linked list traversal

Understanding this problem builds a strong foundation for:

  •  advanced linked list problems
  • pointer-based algorithms
  • interview-level cycle detection problems.