Detect Cycle in Linked List Using Floyd’s Algorithm in DSA

Introduction

The Detect Cycle in a Linked List problem is a popular DSA interview question. It is frequently asked because it tests your understanding of pointers, traversal logic, and problem optimization.

In simple words, this problem asks you to check whether a linked list contains a loop (cycle) or not.

This article explains the problem in very simple, human-friendly language, from basic concepts to interview-level depth, using Floyd’s Cycle Detection Algorithm.

What is a Cycle in a Linked List?

A cycle (loop) in a linked list occurs when a node’s next pointer points to one of the previous nodes instead of pointing to null.

Because of this:

• Traversal never ends

• The list becomes infinite

Example of a Cycle

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

Here, node 5 points back to node 3, creating a cycle.

Why Detecting a Cycle is Important

Detecting cycles is important because:

• Infinite loops can crash programs

• Memory leaks may occur

• Many real-world systems (OS, networking) use cycle detection

Interviewers use this problem to test pointer logic and optimization skills.

Brute Force Approach (Not Recommended)

One simple idea is to store visited nodes in a data structure.

How it Works

• Traverse the list

• Store each visited node in a HashSet

• If a node appears again, a cycle exists

Problems with This Approach

• Extra space is required

• Space Complexity becomes O(n)

Interviewers usually expect a better solution.

Optimized Approach: Floyd’s Cycle Detection Algorithm

The best and most popular solution is Floyd’s Cycle Detection Algorithm, also known as the Tortoise and Hare Algorithm.

Key Idea (Very Simple)

• Use two pointers:

  • Slow pointer moves one step at a time

  • Fast pointer moves two steps at a time

• If a cycle exists, the fast pointer will eventually meet the slow pointer

If they meet → cycle exists
If fast pointer reaches null → no cycle

Why Floyd’s Algorithm Works

In a cycle:

• Fast pointer moves faster

• It will eventually lap the slow pointer

This guarantees a meeting point inside the cycle.

Step-by-Step Explanation

Steps:

1. Initialize both slow and fast at the head

2. Move slow by one step and fast by two steps

3. If slow == fast, a cycle is detected

4. If fast or fast.next becomes null, no cycle exists

Dry Run Example

Linked List:

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

Step	Slow	Fast
1	2	3
2	3	5
3	4	4

Slow and Fast meet → Cycle detected

Code Implementation (Floyd’s Algorithm)

C++ Code

bool hasCycle(ListNode* head) {
    if (!head || !head->next) return false;

    ListNode* slow = head;
    ListNode* fast = head;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;

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

Java Code

public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) return false;

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

Python Code

def hasCycle(head):
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            return True
    return False

Time and Space Complexity

• Time Complexity: O(n)

• Space Complexity: O(1)

This makes Floyd’s Algorithm very efficient.

Important Edge Cases

• Empty linked list

• Single node with no cycle

• Single node pointing to itself

These cases should always be tested.

Common Interview Follow-Up Questions

• Find the starting point of the cycle

• Find the length of the cycle

• Remove the cycle from the linked list

These problems are extensions of Floyd’s Algorithm.

Summary

The Detect Cycle in Linked List problem is a classic DSA question that tests pointer manipulation and optimization skills. Floyd’s Cycle Detection Algorithm provides an efficient way to detect loops using constant space. By understanding how slow and fast pointers work together, you can confidently solve cycle-related linked list problems in coding interviews.