Linked List Cycle Detection

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
    ↑       ↓
    ← ← ← ←

Enter fullscreen mode Exit fullscreen mode

Output:

true

Enter fullscreen mode Exit fullscreen mode

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)

Enter fullscreen mode Exit fullscreen mode

Space Complexity

O(N)

Enter fullscreen mode Exit fullscreen mode

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;
}

Enter fullscreen mode Exit fullscreen mode

Optimal Approach: Floyd’s Cycle Detection Algorithm

Also known as:

Tortoise and Hare Algorithm

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

If there is no cycle:

fast reaches null

Enter fullscreen mode Exit fullscreen mode

If there is a cycle:

fast eventually catches slow

Enter fullscreen mode Exit fullscreen mode

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
        ↑       ↓
        ← ← ← ←

Enter fullscreen mode Exit fullscreen mode

Initial:

slow = 1
fast = 1

Enter fullscreen mode Exit fullscreen mode

After 1 move:

slow = 2
fast = 3

Enter fullscreen mode Exit fullscreen mode

After 2 moves:

slow = 3
fast = 5

Enter fullscreen mode Exit fullscreen mode

After 3 moves:

slow = 4
fast = 4

Enter fullscreen mode Exit fullscreen mode

Both meet.

Cycle detected.

Dry Run

Input

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

Enter fullscreen mode Exit fullscreen mode

Step 1

slow = 1
fast = 1

Enter fullscreen mode Exit fullscreen mode

Step 2

slow = 2
fast = 3

Enter fullscreen mode Exit fullscreen mode

Step 3

slow = 3
fast = 5

Enter fullscreen mode Exit fullscreen mode

Step 4

slow = 4
fast = 4

Enter fullscreen mode Exit fullscreen mode

Pointers meet.

return true

Enter fullscreen mode Exit fullscreen mode

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;
    }
}

Enter fullscreen mode Exit fullscreen mode

Complexity Analysis

Time Complexity

O(N)

Enter fullscreen mode Exit fullscreen mode

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

Space Complexity

O(1)

Enter fullscreen mode Exit fullscreen mode

No extra data structure is used.

Interview Follow-Up

Why do we check?

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

Enter fullscreen mode Exit fullscreen mode

Because fast moves two steps at a time.

Before moving:

fast = fast.next.next;

Enter fullscreen mode Exit fullscreen mode

we must ensure both nodes exist to avoid a NullPointerException.

Mathematical Insight

Inside the cycle:

Fast speed = 2
Slow speed = 1

Enter fullscreen mode Exit fullscreen mode

Relative speed:

2 - 1 = 1

Enter fullscreen mode Exit fullscreen mode

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.