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. 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

2. You are given a singly linked list and need to determine if it reads the same forwards and backwards. Which approach guarantees an optimal solution with O(n) time and O(1) space complexity?

easy

A. Use fast and slow pointers to find the middle, reverse the second half in-place, then compare both halves.

B. Convert the linked list to an array and check palindrome by comparing elements from both ends.

C. Use a hash set to store visited nodes and check for palindrome by comparing values.

D. Use a recursive approach to compare nodes from start and end simultaneously.

Solution

1. Step 1: Identify the problem constraints

   The problem requires checking palindrome in O(n) time and O(1) space.

2. Step 2: Evaluate approaches

   Converting to array uses O(n) space, recursion uses O(n) stack space, and hash set is not suitable for palindrome check. Using fast and slow pointers to reverse second half in-place meets both time and space requirements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Optimal approach uses fast-slow pointers and in-place reversal [OK]

Hint: Optimal palindrome check uses fast-slow pointers and in-place reversal [OK]

Common Mistakes:

• Assuming array conversion is optimal due to simplicity
• Believing recursion uses constant space
• Using hash sets for palindrome detection

3. Given the following code snippet for splitting a linked list into k parts, and the input list 1->2->3 with k=5, what is the value of parts[2] (the head node's value of the third part) in the returned array?

easy

A. null

B. 3

C. 2

D. 1

Solution

1. Step 1: Count total nodes and compute sizes

   List length = 3, k = 5, so part_size = 0, remainder = 3.

2. Step 2: Assign nodes to parts

   First 3 parts get 1 node each (due to remainder), last 2 parts get null (empty).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   parts[0]=1, parts[1]=2, parts[2]=3, parts[3]=null, parts[4]=null, so parts[2] points to node with value 3 [OK]

Hint: Parts beyond list length are null [OK]

Common Mistakes:

• Assuming all parts have nodes
• Off-by-one in indexing parts
• Confusing node values with indices

4. What is the time complexity of the optimal Happy Number detection algorithm that uses a known cycle set and repeatedly computes the sum of squares of digits until it reaches 1 or a cycle number? Assume n is the input number and k is the number of iterations until termination.

medium

A. O(n) because each digit is processed once per iteration

B. O(k * log n) because each iteration processes digits proportional to log n and there are k iterations

C. O(k * n) because sum of squares depends on n itself

D. O(k) because the cycle detection set lookup is constant time and digits are fixed length

Solution

1. Step 1: Identify cost per iteration

   Each iteration computes sum of squares of digits. Number of digits in n is proportional to log n, so each iteration is O(log n).

2. Step 2: Multiply by number of iterations k

   The process repeats k times until reaching 1 or cycle. Total time is O(k * log n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sum of digits per iteration is log n, repeated k times -> O(k * log n) [OK]

Hint: Sum of digits cost is O(log n), not O(n) [OK]

Common Mistakes:

• Confusing n with number of digits, assuming O(n) per iteration

5. What is the space complexity of the stack-based approach to find the nth node from the end in a singly linked list of length n?

medium

A. O(n) because all nodes are stored in the stack

B. O(1) because only a few pointers are used

C. O(n) because recursion stack is used

D. O(log n) due to divide and conquer traversal

Solution

1. Step 1: Identify data structures used

   The stack stores every node in the list, so it holds n nodes.

2. Step 2: Determine space complexity

   Storing all n nodes means O(n) auxiliary space is required.

3. Step 3: Re-examine options

   O(n) because all nodes are stored in the stack states O(n) space which is correct for stack-based approach. O(1) because only a few pointers are used states O(1) which is incorrect for stack-based approach.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Stack size grows linearly with list length [OK]

Hint: Stack stores all nodes, so space is O(n) [OK]

Common Mistakes:

• Assuming constant space due to pointers
• Confusing recursion stack with iterative stack
• Thinking divide and conquer applies here