Linked List Cycle Detection

🎯

Linked List Cycle Detection

easyTWO_POINTERAmazonMicrosoftGoogle

Imagine you are debugging a network of pipes where water flows in loops. Detecting if water can endlessly circulate in a loop is like detecting a cycle in a linked list.

💡 This problem is about detecting if a linked list has a cycle, which can cause infinite loops in programs. Beginners often struggle because naive traversal can get stuck in cycles, so special techniques are needed to detect them efficiently.

📋

Problem Statement

Given the head of a singly linked list, determine if the linked list has a cycle in it. Return true if there is a cycle, otherwise return false.

The number of nodes in the list is in the range [0, 10^5].Node values are arbitrary and do not affect cycle detection.You must solve the problem using O(1) (constant) memory if possible.

💡

Example

Input"head = [3,2,0,-4], where the tail connects to the node at position 1 (0-indexed)"

Outputtrue

The linked list contains a cycle because the last node points back to the second node.

Input"head = [1,2], where the tail connects to the node at position 0"

Outputtrue

The linked list contains a cycle because the last node points back to the first node.

Input"head = [1], with no cycle"

Outputfalse

The linked list does not contain a cycle.

• Empty list (head = null) → false
• Single node with no cycle → false
• Single node with cycle to itself → true
• Two nodes with no cycle → false
• Two nodes with cycle (tail points to head) → true

⚠️

Common Mistakes

Not checking if fast or fast.next is null before moving fast pointer

Runtime error due to null pointer dereference

✅ Always check fast and fast.next are not null before advancing fast pointer

Using slow == fast before moving pointers in the loop

Incorrectly detects cycle at start even if none exists

✅ Move pointers first, then check if they meet

Modifying node values or structure without permission

May corrupt input or be disallowed in interviews

✅ Use pointer techniques or extra memory instead of modifying nodes

Using extra memory approach when asked for O(1) space

Fails to meet interview constraints

✅ Learn and implement Floyd’s cycle detection algorithm

Not handling empty list or single node cases

Code may crash or give wrong answer

✅ Add checks for null head and single node scenarios

🧠

Brute Force (Hash Set to Detect Revisited Nodes)

💡 This approach uses extra memory to remember visited nodes, which is straightforward and helps beginners understand the problem before optimizing.

Intuition

If we traverse the linked list and keep track of all nodes visited, encountering a node twice means there is a cycle.

Algorithm

1. Initialize an empty hash set to store visited nodes.
2. Traverse the linked list from the head node.
3. For each node, check if it is already in the hash set.
4. If yes, return true (cycle detected).
5. If no, add the node to the hash set and continue.
6. If traversal ends (null reached), return false (no cycle).

💡 This algorithm is easy to understand but uses extra space, which is not optimal but helps grasp the problem.

</>

Code

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

def hasCycle(head):
    visited = set()
    current = head
    while current:
        if current in visited:
            return True
        visited.add(current)
        current = current.next
    return False

# Example usage:
if __name__ == '__main__':
    node1 = ListNode(3)
    node2 = ListNode(2)
    node3 = ListNode(0)
    node4 = ListNode(-4)
    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node2  # cycle
    print(hasCycle(node1))  # Output: True

Line Notes

visited = set()Initialize a set to keep track of nodes we've seen to detect repeats.

while current:Traverse the linked list until we reach the end (null).

if current in visited:If current node is already visited, a cycle exists.

visited.add(current)Mark the current node as visited before moving on.

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; this.next = null; }
}

public class Solution {
    public boolean hasCycle(ListNode head) {
        java.util.HashSet<ListNode> visited = new java.util.HashSet<>();
        ListNode current = head;
        while (current != null) {
            if (visited.contains(current)) {
                return true;
            }
            visited.add(current);
            current = current.next;
        }
        return false;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(0);
        ListNode node4 = new ListNode(-4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2; // cycle
        Solution sol = new Solution();
        System.out.println(sol.hasCycle(node1)); // true
    }
}

Line Notes

java.util.HashSet<ListNode> visited = new java.util.HashSet<>()Create a set to store visited nodes for cycle detection.

while (current != null)Traverse the linked list until the end is reached.

if (visited.contains(current))Check if current node was already visited indicating a cycle.

visited.add(current)Add current node to visited set before moving forward.

#include <iostream>
#include <unordered_set>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

bool hasCycle(ListNode* head) {
    std::unordered_set<ListNode*> visited;
    ListNode* current = head;
    while (current != nullptr) {
        if (visited.find(current) != visited.end()) {
            return true;
        }
        visited.insert(current);
        current = current->next;
    }
    return false;
}

int main() {
    ListNode* node1 = new ListNode(3);
    ListNode* node2 = new ListNode(2);
    ListNode* node3 = new ListNode(0);
    ListNode* node4 = new ListNode(-4);
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node2; // cycle
    std::cout << std::boolalpha << hasCycle(node1) << std::endl; // true
    return 0;
}

Line Notes

std::unordered_set<ListNode*> visited;Use a hash set to track visited nodes for cycle detection.

while (current != nullptr)Traverse nodes until the end of the list.

if (visited.find(current) != visited.end())If current node is found in visited set, cycle exists.

visited.insert(current)Insert current node into visited set before moving on.

function ListNode(val) {
    this.val = val;
    this.next = null;
}

function hasCycle(head) {
    const visited = new Set();
    let current = head;
    while (current !== null) {
        if (visited.has(current)) {
            return true;
        }
        visited.add(current);
        current = current.next;
    }
    return false;
}

// Example usage:
const node1 = new ListNode(3);
const node2 = new ListNode(2);
const node3 = new ListNode(0);
const node4 = new ListNode(-4);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node2; // cycle
console.log(hasCycle(node1)); // true

Line Notes

const visited = new Set();Create a set to keep track of visited nodes for cycle detection.

while (current !== null)Traverse the linked list until the end is reached.

if (visited.has(current))Check if current node was already visited indicating a cycle.

visited.add(current)Add current node to visited set before moving forward.

⏱

Complexity

TimeO(n)

SpaceO(n)

We visit each node once, but store each node in a hash set, so time is linear and space is linear in number of nodes.

💡 For n=100,000 nodes, this means up to 100,000 insertions and lookups in the set, which is feasible but uses extra memory.

Interview Verdict: Accepted but not optimal due to extra space

This approach works but uses extra memory, so interviewers expect you to improve it.

🧠

Fast and Slow Pointer (Floyd’s Cycle Detection Algorithm)

💡 This is the classic optimal approach that uses two pointers moving at different speeds to detect cycles without extra memory.

Intuition

If there is a cycle, a fast pointer moving two steps at a time will eventually meet the slow pointer moving one step at a time inside the cycle.

Algorithm

1. Initialize two pointers, slow and fast, both at the head.
2. Move slow pointer one step and fast pointer two steps in each iteration.
3. If fast or fast.next becomes null, return false (no cycle).
4. If slow and fast meet at any point, return true (cycle detected).

💡 The key insight is that the fast pointer will catch up to the slow pointer if a cycle exists.

</>

Code

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

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

# Example usage:
if __name__ == '__main__':
    node1 = ListNode(3)
    node2 = ListNode(2)
    node3 = ListNode(0)
    node4 = ListNode(-4)
    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node2  # cycle
    print(hasCycle(node1))  # Output: True

Line Notes

slow = headInitialize slow pointer at the start of the list.

fast = headInitialize fast pointer at the start of the list.

while fast and fast.next:Continue loop only if fast pointer and its next node exist to avoid null errors.

if slow == fast:If pointers meet, a cycle exists.

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; this.next = null; }
}

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

    public static void main(String[] args) {
        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(0);
        ListNode node4 = new ListNode(-4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2; // cycle
        Solution sol = new Solution();
        System.out.println(sol.hasCycle(node1)); // true
    }
}

Line Notes

ListNode slow = head;Start slow pointer at head to traverse one step at a time.

ListNode fast = head;Start fast pointer at head to traverse two steps at a time.

while (fast != null && fast.next != null)Ensure fast pointer can move two steps safely without null pointer exceptions.

if (slow == fast)Pointers meeting means a cycle is detected.

#include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

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

int main() {
    ListNode* node1 = new ListNode(3);
    ListNode* node2 = new ListNode(2);
    ListNode* node3 = new ListNode(0);
    ListNode* node4 = new ListNode(-4);
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node2; // cycle
    std::cout << std::boolalpha << hasCycle(node1) << std::endl; // true
    return 0;
}

Line Notes

ListNode* slow = head;Initialize slow pointer at the start of the list.

ListNode* fast = head;Initialize fast pointer at the start of the list.

while (fast != nullptr && fast->next != nullptr)Loop continues only if fast pointer can safely move two steps.

if (slow == fast)Pointers meeting indicates a cycle.

function ListNode(val) {
    this.val = val;
    this.next = null;
}

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

// Example usage:
const node1 = new ListNode(3);
const node2 = new ListNode(2);
const node3 = new ListNode(0);
const node4 = new ListNode(-4);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node2; // cycle
console.log(hasCycle(node1)); // true

Line Notes

let slow = head;Initialize slow pointer at the start of the list.

let fast = head;Initialize fast pointer at the start of the list.

while (fast !== null && fast.next !== null)Ensure fast pointer can move two steps safely.

if (slow === fast)Pointers meeting means a cycle is detected.

⏱

Complexity

TimeO(n)

SpaceO(1)

Each node is visited at most once by slow pointer, and fast pointer moves faster but also bounded by list length, so linear time. No extra space used.

💡 For n=100,000 nodes, this means about 100,000 steps, but only constant extra memory, making it very efficient.

Interview Verdict: Accepted and optimal

This is the preferred approach in interviews due to its efficiency and elegance.

🧠

Modifying Node Structure (Marking Visited Nodes)

💡 This approach modifies the node structure by adding a visited flag, which is not always allowed but helps understand cycle detection by marking nodes.

Intuition

If we can mark nodes as visited during traversal, encountering a marked node means a cycle exists.

Algorithm

1. Traverse the linked list from head.
2. For each node, check if it is marked visited.
3. If yes, return true (cycle detected).
4. If no, mark the node as visited and continue.
5. If traversal ends, return false (no cycle).

💡 This approach is simple but requires modifying input nodes, which is often disallowed in interviews.

</>

Code

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
        self.visited = False

def hasCycle(head):
    current = head
    while current:
        if current.visited:
            return True
        current.visited = True
        current = current.next
    return False

# Example usage:
if __name__ == '__main__':
    node1 = ListNode(3)
    node2 = ListNode(2)
    node3 = ListNode(0)
    node4 = ListNode(-4)
    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node2  # cycle
    print(hasCycle(node1))  # Output: True

Line Notes

self.visited = FalseAdd a visited flag to each node to track if it has been seen.

if current.visited:If node is already visited, a cycle exists.

current.visited = TrueMark the current node as visited before moving on.

while current:Traverse the linked list until the end.

class ListNode {
    int val;
    ListNode next;
    boolean visited;
    ListNode(int val) { this.val = val; this.next = null; this.visited = false; }
}

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode current = head;
        while (current != null) {
            if (current.visited) {
                return true;
            }
            current.visited = true;
            current = current.next;
        }
        return false;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(0);
        ListNode node4 = new ListNode(-4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2; // cycle
        Solution sol = new Solution();
        System.out.println(sol.hasCycle(node1)); // true
    }
}

Line Notes

boolean visited;Add a boolean flag to mark if node has been visited.

if (current.visited)Check if current node was already visited indicating a cycle.

current.visited = true;Mark current node as visited before moving forward.

while (current != null)Traverse the linked list until the end.

#include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    bool visited;
    ListNode(int x) : val(x), next(nullptr), visited(false) {}
};

bool hasCycle(ListNode* head) {
    ListNode* current = head;
    while (current != nullptr) {
        if (current->visited) {
            return true;
        }
        current->visited = true;
        current = current->next;
    }
    return false;
}

int main() {
    ListNode* node1 = new ListNode(3);
    ListNode* node2 = new ListNode(2);
    ListNode* node3 = new ListNode(0);
    ListNode* node4 = new ListNode(-4);
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node2; // cycle
    std::cout << std::boolalpha << hasCycle(node1) << std::endl; // true
    return 0;
}

Line Notes

bool visited;Add a flag to each node to track if it has been visited.

if (current->visited)If node is already visited, a cycle exists.

current->visited = true;Mark current node as visited before moving on.

while (current != nullptr)Traverse the linked list until the end.

function ListNode(val) {
    this.val = val;
    this.next = null;
    this.visited = false;
}

function hasCycle(head) {
    let current = head;
    while (current !== null) {
        if (current.visited) {
            return true;
        }
        current.visited = true;
        current = current.next;
    }
    return false;
}

// Example usage:
const node1 = new ListNode(3);
const node2 = new ListNode(2);
const node3 = new ListNode(0);
const node4 = new ListNode(-4);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node2; // cycle
console.log(hasCycle(node1)); // true

Line Notes

this.visited = false;Add a visited flag to each node to track visits.

if (current.visited)Check if current node was already visited indicating a cycle.

current.visited = true;Mark current node as visited before moving forward.

while (current !== null)Traverse the linked list until the end.

⏱

Complexity

TimeO(n)

SpaceO(1)

Each node is visited once and marked, so linear time and constant extra space since no external data structures are used.

💡 For n=100,000 nodes, this means 100,000 steps and no extra memory beyond the node flags.

Interview Verdict: Accepted but modifies input nodes, often disallowed

This approach is efficient but not always allowed because it changes the input data structure.

📊

All Approaches - One-Glance Tradeoffs

💡 The fast and slow pointer approach is the best to code in interviews due to its optimal time and space.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Hash Set)	O(n)	O(n)	No	N/A	Mention only - never code unless asked for simple solution
2. Fast and Slow Pointer (Floyd’s Algorithm)	O(n)	O(1)	No	N/A	Code this approach for optimal solution
3. Modifying Node Structure (Visited Flag)	O(n)	O(1)	No	N/A	Mention only if allowed to modify input; usually disallowed

💼

Interview Strategy

💡 Use this guide to understand the problem deeply and practice explaining each approach clearly before coding.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Present the brute force approach using a hash set to detect cycles.Step 3: Explain the limitations of extra space and introduce Floyd’s fast and slow pointer method.Step 4: Code the optimal fast and slow pointer solution.Step 5: Discuss edge cases and test your code thoroughly.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of cycle detection, ability to optimize space, and handle edge cases without errors.

Common Follow-ups

• How to find the node where the cycle begins → Use Floyd’s algorithm with a second phase.
• What if the list is doubly linked → Cycle detection still applies similarly.

💡 Follow-ups test deeper understanding of cycle properties and pointer manipulation.

🔍

Pattern Recognition

When to Use

1) Problem involves linked list traversal 2) Need to detect cycles or repeated nodes 3) Constraints require O(1) space 4) Keywords like 'cycle', 'loop', or 'repeated node'

Signature Phrases

detect if linked list has a cyclereturn true if cycle existsfast and slow pointers

NOT This Pattern When

Problems that require reversing linked lists or merging sorted lists are different patterns.

Similar Problems

Linked List Cycle II - find the node where the cycle beginsHappy Number - uses cycle detection in number sequencesDetect Cycle in a Graph - similar concept but different data structure

Practice

1. Consider the following Python function that deletes N nodes after skipping M nodes in a linked list. Given the linked list 1 -> 2 -> 3 -> 4 and parameters M=1, N=1, what is the linked list after calling delete_n_after_m_optimized(head, 1, 1)?

easy

A. 1 -> 3 -> 4

B. 2 -> 3 -> 4

C. 1 -> 2 -> 4

D. 1 -> 4

Solution

1. Step 1: Trace skipping M=1 node

   Starting at node 1, skip 1 node means stay at node 1 (loop runs zero times).

2. Step 2: Delete N=1 node after current

   Delete node after 1, which is node 2. So, link node 1's next to node 3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Resulting list is 1 -> 3 -> 4 after deletion [OK]

Hint: Skipping M=1 means no move; delete next N=1 node [OK]

Common Mistakes:

• Off-by-one in skipping nodes
• Deleting wrong nodes after skipping
• Misunderstanding loop ranges

2. Given the following code for finding the middle node of a linked list, what is the value returned when the input list is 1 -> 2 -> 3 -> 4?

easy

A. 2

B. 3

C. 4

D. 1

Solution

1. Step 1: Trace slow and fast pointers

   Initial: slow=1, fast=1; Iteration 1: slow=2, fast=3; Iteration 2: fast.next is null, loop ends.

2. Step 2: Return slow's value

   Slow points to node with value 3 at loop end.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   For even length, returns second middle node (3) [OK]

Hint: Fast pointer moves twice as fast; slow ends at middle [OK]

Common Mistakes:

• Returning first middle node for even length
• Off-by-one errors in loop condition
• Confusing slow and fast pointer positions

3. Given the following Python code for reorderList and the input list 1->2->3->4, what is the value of the node pointed to by left after the first merge step in the recursion unwinding?

easy

A. Node with value 3

B. Node with value 2

C. Node with value 4

D. Node with value 1

Solution

1. Step 1: Trace recursion to the end

   Recursion reaches right = None, then unwinds from node 4 back to node 1.

2. Step 2: First merge step during unwinding

   At right=4, left=1, tmp=left.next=2; left.next=4; 4.next=2; left=2 after merge.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   After first merge, left points to node with value 2 [OK]

Hint: left moves forward after merging right node [OK]

Common Mistakes:

• Confusing left pointer update
• Off-by-one in recursion unwind
• Misreading next pointer assignments

4. If the linked list allows cycles (i.e., it may not terminate), which modification is necessary to safely find the nth node from the end?

hard

A. Use the two-pointer approach without changes; it will still work.

B. Use a stack to store nodes indefinitely until nth node is found.

C. First detect cycle using Floyd's cycle detection, then handle accordingly before finding nth node.

D. Increase n to a very large number to ensure traversal covers the cycle.

Solution

1. Step 1: Understand cycle impact

   If the list has a cycle, naive traversal will loop infinitely, breaking the algorithm.

2. Step 2: Detect and handle cycle

   Use Floyd's cycle detection to identify cycle presence and length, then adjust logic to avoid infinite loops.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Cycle detection is prerequisite for safe traversal [OK]

Hint: Detect cycle first to avoid infinite loops [OK]

Common Mistakes:

• Assuming list always terminates
• Using stack without cycle check
• Increasing n arbitrarily

5. If the linked list nodes can be reused multiple times (i.e., the list is cyclic or can be traversed repeatedly), which modification is necessary to the optimal palindrome check algorithm?

hard

A. No modification needed; the current algorithm works as is.

B. Use a stack to store first half values instead of reversing to avoid modifying the list.

C. Convert the list to an array to handle multiple traversals safely.

D. Restore the reversed second half to original order after comparison to preserve list structure.

Solution

1. Step 1: Understand reuse implications

   If nodes are reused or list is cyclic, modifying it breaks future traversals.

2. Step 2: Restore list after palindrome check

   Reversing second half in-place must be undone to preserve original list structure.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Restoring reversed half ensures list integrity for reuse [OK]

Hint: Always restore list after in-place reversal if list is reused [OK]

Common Mistakes:

• Ignoring list restoration causing side effects
• Switching to stack approach unnecessarily increasing space
• Assuming array conversion is always better