Introduction

The Linked List Cycle problem involves detecting whether a linked list contains a loop.

The task is to:

  • determine if cycle exists
  • use pointer traversal
  • avoid infinite traversal

Example:

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

Output:
True

Explanation:

Node 4 points back to node 2. Traversal never ends.So cycle exists.

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
  • if node appears again:
    cycle exists

Steps:

  1. Start traversal.
  2. Store current node.
  3. If node already exists:
    return true.
  4. Otherwise continue traversal.

This approach works but:

  • uses extra memory

So Fast & Slow Pointer 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 visited
Cycle detected

Practice :

Complexity Analysis :

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

Space Complexity:- O(n)
Explanation :
HashSet is used to store visited nodes.

Approach 2 : Optimal Solution(Using Fast & Slow Pointer)

Explanations:

Explanation:

This is the most optimized and interview-preferred solution.

The idea is:

  • use two pointers:
    slow
    fast
  • slow moves one step
  • fast moves two steps

If cycle exists:

  • both pointers meet

If fast reaches NULL:

  • no cycle exists

Dry Run

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

Slow:
1 -> 2 -> 3

Fast:
1 -> 3 -> 2

Eventually:
slow == fast

Cycle detected

Practice :

Complexity Analysis :

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

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

Why This Problem is Important

This problem builds the foundation for:

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

Real-World Applications

Cycle detection is used in:

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

Common Beginner Mistakes

  • Incorrect fast pointer movement
  • Forgetting NULL checks
  • Infinite loops
  • Wrong comparison logic
  • Losing pointer references

Interview Tip

Interviewers often expect:

  • Fast & Slow Pointer optimization
  • O(1) space solution
  • Floyd Cycle Detection explanation
  • proper pointer traversal

Always explain:

  • why fast pointer moves two steps
  • how pointers eventually meet in a cycle

Related Questions

  • Detect Cycle II
  • Happy Number
  • Middle of Linked List
  • Remove Nth Node
  • Reverse Linked List

Final Takeaway

The Linked List Cycle problem is one of the most important Fast & Slow Pointer problems.

It teaches:

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

Understanding this problem builds a strong foundation for:

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