Detect Cycle in Linked List — Problem Statement & Solution Guide

Linked ListMediumMixed

TimeO(n)

SpaceO(1)

Problem Description

You are given the head pointer of a singly linked list. Determine whether the list contains a cycle. A cycle is defined as a condition where the next pointer of any node in the list points to a previously visited node, thereby creating an infinite loop. If the list is acyclic, the traversal will eventually reach a node whose next pointer is null.

Return true if a cycle is detected within the structure, and false if the list terminates normally. Your solution must not modify the structure of the linked list.

DSA Pattern Breakdown

"Detect Cycle in Linked List"

medium

WHY DOES IT MATTER?

Cycle detection is a fundamental graph‑traversal pattern that appears in memory management, networking, and concurrency control. Recognizing and applying the two‑pointer technique prevents infinite loops, memory leaks, and deadlocks, making it a staple for robust system design.

OPTIMIZATION CHALLENGE

The key insight is to eliminate auxiliary storage by exploiting relative motion; advancing pointers at different speeds creates a deterministic collision point inside any cycle, reducing space from O(n) to O(1) while preserving linear time.

REAL-WORLD CONNECTION

Think of a train on a circular track: if two trains start at different points and one moves twice as fast, they will inevitably meet. Similarly, in distributed micro‑service call graphs, a request that circles back to a previous service forms a logical cycle that must be detected to avoid endless retries.

During an interview, first write the null‑check guard clauses, then implement the while loop with slow = slow.next and fast = fast.next?.next. If you get stuck, sketch the list on paper and trace a few steps—visualizing the “lap” helps avoid off‑by‑one errors.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The classic solution to detecting a cycle in a singly linked list relies on Floyd's Tortoise and Hare algorithm, also known as the two‑pointer technique. By advancing one pointer (the tortoise) one step at a time and another pointer (the hare) two steps at a time, any existing loop forces the faster pointer to eventually lap the slower one, guaranteeing a meeting point inside the cycle. This works because in a cyclic structure the relative speed difference creates a deterministic rendezvous, analogous to two runners on a circular track.

Naïve approaches—such as storing every visited node in a hash set or repeatedly traversing the list to count nodes—either consume O(n) extra space or degrade to O(n²) time when the list is long and the cycle is near the tail. These methods become impractical for massive data streams or memory‑constrained environments. Floyd's algorithm, by contrast, achieves O(1) auxiliary space while preserving linear time, making it the optimal paradigm for cycle detection in linked structures.

The underlying theory also extends to any structure that can be modeled as a functional graph, where each node has exactly one outgoing edge. The meeting point detection is a manifestation of the pigeonhole principle: with n+1 steps in a list of n distinct nodes, at least one node must be revisited, and the two‑pointer scheme exploits this inevitability without explicit bookkeeping.

Interview Questions on This Problem

Q1How would you modify Floyd's algorithm to also return the node where the cycle begins?

After the tortoise and hare meet, reset one pointer to the head and then advance both pointers one step at a time; the node where they meet again is the entry point of the cycle. This works because both pointers are now the same distance from the cycle start.

Q2What are the trade‑offs between using a hash set versus the two‑pointer technique for cycle detection in a linked list?

A hash set offers O(n) time and O(n) space, which is simple to implement but can cause memory pressure on large lists. The two‑pointer technique provides O(n) time with O(1) extra space, but requires careful handling of null checks to avoid dereferencing errors.

Q3In a distributed system where nodes represent services and edges represent calls, how could you detect a request loop without central coordination?

You can embed a unique request identifier and a hop‑count in each call; each service forwards the request while incrementing the hop‑count. If a service receives a request with an identifier it has already processed or a hop‑count exceeding a threshold, a loop is detected—mirroring the two‑pointer concept in a decentralized setting.

Examples

Example 1

Input

head = [3, 4, 5, 6], tail.next = head[1]

Output

true

Explanation: The list starts at node 3. The traversal proceeds 3 -> 4 -> 5 -> 6. The `next` pointer of node 6 points back to node 4. Since node 4 has already been visited, a cycle is confirmed. The function returns true.

Example 2

Input

head = [1, 2, 3, 4, 5], tail.next = null

Output

false

Explanation: The list is linear. The traversal proceeds 1 -> 2 -> 3 -> 4 -> 5. The `next` pointer of node 5 is null, indicating the end of the list. No node points to a previously visited node. The function returns false.

Example 3

Input

head = [7], tail.next = head[0]

Output

true

Explanation: The list contains a single node with value 7. The `next` pointer of this node points to itself. This creates a self-referential cycle. The function returns true.

Example 4

Input

head = [10, 20, 30, 40, 50, 60], tail.next = head[2]

Output

true

Explanation: The list starts at 10. The sequence is 10 -> 20 -> 30 -> 40 -> 50 -> 60. The `next` pointer of node 60 points to node 30. Since node 30 was visited earlier in the sequence, a cycle exists. The function returns true.

Constraints

0 <= number of nodes in the list <= 10^5
-10^9 <= Node.val <= 10^9
The `next` pointer of any node is either null or points to another node in the list
The input list is guaranteed to be a valid linked list structure (no dangling pointers)

Optimal Approach & Strategy

Use two pointers moving at different speeds (slow = 1 step, fast = 2 steps); if they ever point to the same node, a cycle exists.

Brute Force Approach

Store every visited node in a hash set and check each new node against the set; if it already exists, a cycle is found.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

function hasCycle(head) {
       let slow = head;
       let fast = head;
       while (fast !== null && fast.next !== null) {
           slow = slow.next;
           fast = fast.next.next;
           if (slow === fast) {
               return true;
           }
       }
       return false;
   }

class Solution {
   public:
       bool hasCycle(ListNode *head) {
           ListNode *slow = head;
           ListNode *fast = head;
           while (fast != nullptr && fast->next != nullptr) {
               slow = slow->next;
               fast = fast->next->next;
               if (slow == fast) {
                   return true;
               }
           }
           return false;
       }
   }

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

class ListNode:
       def __init__(self, x):
           self.val = x
           self.next = None

   def hasCycle(head):
       slow = head
       fast = head
       while fast is not None and fast.next is not None:
           slow = slow.next
           fast = fast.next.next
           if slow == fast:
               return True
       return False

function hasCycle(head) {
       let slow = head;
       let fast = head;
       while (fast !== null && fast.next !== null) {
           slow = slow.next;
           fast = fast.next.next;
           if (slow === fast) {
               return true;
           }
       }
       return false;
   }

Asked in Top Tech Interviews

uncategorizedmediumgeneric

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Detect Cycle in Linked List Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Linked List

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Detect Cycle in Linked List — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor