Linked List Cycle Detection

leetcode.com

Cycle detection is one of the most classic Linked List interview problems.

At first, it may look like we need extra memory to track visited nodes. However, there's a brilliant two-pointer technique that solves it in O(1) space.

Let's understand it step by step.

---

Problem Statement

Given the head of a linked list, determine whether the linked list contains a cycle.

A cycle exists if some node in the list can be reached again by continuously following the next pointer.

Example

1 → 2 → 3 → 4
    ↑       ↓
    ← ← ← ←

Output:

true

Because the list loops back to node 2.

---

Brute Force Approach

Interview Explanation

One way to detect a cycle is to store every visited node inside a HashSet.

While traversing the linked list:

• If the current node is already present in the HashSet, a cycle exists.
• Otherwise, add it to the set and continue.

Since we're storing node references, we can easily identify if we've visited a node before.

Time Complexity

O(N)

Space Complexity

O(N)

Java Code

import java.util.HashSet;

public boolean hasCycle(ListNode head) {

    HashSet<ListNode> visited = new HashSet<>();

    while (head != null) {

        if (visited.contains(head)) {
            return true;
        }

        visited.add(head);
        head = head.next;
    }

    return false;
}

---

Optimal Approach: Floyd's Cycle Detection Algorithm

Also known as:

Tortoise and Hare Algorithm

This is one of the most important Linked List patterns for interviews.

---

Key Observation

Use two pointers:

slow → moves 1 step
fast → moves 2 steps

If there is no cycle:

fast reaches null

If there is a cycle:

fast eventually catches slow

inside the loop.

---

Why Does It Work?

Imagine a circular running track.

Two runners start together:

• Slow runner moves 1 step.
• Fast runner moves 2 steps.

Since the fast runner gains one position every move, it must eventually catch the slow runner.

The same idea applies to Linked Lists.

Once both pointers enter the cycle, the distance between them keeps shrinking until they meet.

---

Visual Intuition

1 → 2 → 3 → 4 → 5
        ↑       ↓
        ← ← ← ←

Initial:

slow = 1
fast = 1

After 1 move:

slow = 2
fast = 3

After 2 moves:

slow = 3
fast = 5

After 3 moves:

slow = 4
fast = 4

Both meet.

Cycle detected.

---

Dry Run

Input

1 → 2 → 3 → 4 → 5
        ↑       ↓
        ← ← ← ←

Step 1

slow = 1
fast = 1

Step 2

slow = 2
fast = 3

Step 3

slow = 3
fast = 5

Step 4

slow = 4
fast = 4

Pointers meet.

return true

---

Optimal Java Solution

public class Solution {

    public boolean hasCycle(ListNode head) {

        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {

            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                return true;
            }
        }

        return false;
    }
}

---

Complexity Analysis

Time Complexity

O(N)

Each pointer traverses at most the linked list length before meeting or reaching the end.

Space Complexity

O(1)

No extra data structure is used.

---

Interview Follow-Up

Why do we check?

fast != null && fast.next != null

Because fast moves two steps at a time.

Before moving:

fast = fast.next.next;

we must ensure both nodes exist to avoid a NullPointerException.

---

Mathematical Insight

Inside the cycle:

Fast speed = 2
Slow speed = 1

Relative speed:

2 - 1 = 1

So every iteration the fast pointer gains one node on the slow pointer.

Since the cycle length is finite, they must eventually collide.

---

Takeaway

Whenever you need to detect a cycle in a Linked List, think of two runners on a circular track. If one runner moves twice as fast as the other, they are guaranteed to meet if a cycle exists.

This elegant O(1) space solution is known as Floyd's Tortoise and Hare Algorithm and is one of the most frequently asked Linked List interview patterns.