Linked List Cycle

Problem Statement

Given the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

What to notice first

• A cycle exists when a node’s next pointer eventually points back to a node we’ve already visited.
• Floyd’s Algorithm uses two pointers at different speeds: if they ever meet, a cycle exists. This works because in a circular list, the fast pointer will eventually “lap” the slow pointer.
• The Hash Set approach tracks visited nodes; if we encounter a node twice, a cycle exists.
• Both approaches have the same O(n) time complexity, but Floyd’s saves space with O(1) vs. O(n).

Examples

Input	Output	Explanation
Head: [3,2,0,-4], pos: 1	true	Cycle: 2 → 0 → -4 → 2
Head: [1,2], pos: 0	true	Cycle: 2 → 1 → 2
Head: [1], pos: -1	false	No cycle

Constraints

• The number of the nodes in the list is in the range [0, 10^4].
• -10^5 <= Node.val <= 10^5
• pos is -1 or a valid index in the linked-list.

Real-World Applications

Where this pattern appears

• Garbage collection — detect circular references in memory to prevent infinite loops during cleanup.
• Graph traversal — identify cycles in directed graphs to ensure algorithms terminate.
• Data structure validation — verify linked lists are well-formed (no accidental cycles).
• Deadlock detection — in concurrent systems, identify circular wait conditions between threads or resources.
• Infinite loop prevention — detect cycles in dependency chains (e.g., in build systems or package managers).

Complexity Comparison

Approach	Time	Space	Best When
Floyd’s Algorithm	O(n)	O(1)	Space is limited; elegant two-pointer technique
Hash Set	O(n)	O(n)	Space is available; easier to understand

Which approach should you learn first?

• Learn Floyd’s Algorithm first — it is the optimal solution and a classic interview technique.
• Use Hash Set as a fallback if you forget the two-pointer logic; it is straightforward and correct.

Space Efficient & Optimal

Floyd’s Algorithm

O(n) time · O(1) space

Easy to Implement

Hash Set

O(n) time · O(n) space

Approach 1: Floyd’s Algorithm (Tortoise & Hare)

★ Recommended

Use two pointers starting at the head: a slow pointer that advances one step at a time, and a fast pointer that advances two steps at a time. If a cycle exists, the fast pointer will eventually catch up to (meet) the slow pointer. If no cycle exists, the fast pointer will reach the end (null).

⏱ Time O(n) Single pass with two pointers 💾 Space O(1) Only two pointer variables

Step-by-step Example

Input: [3, 2, 0, -4] with cycle at index 1

Step	Slow Position	Fast Position	Notes
Start	3	3	Both start at head
Step 1	2	0	Slow moves 1, fast moves 2
Step 2	0	2	Slow moves 1, fast moves 2
Step 3	-4	-4	Slow moves 1, fast moves 2
Step 4	2	0	Both in cycle, continue
Step 5	0	-4	Fast closing in
Step 6	-4	2	Still moving
Step 7	2	0	Pointers converge
Step 8	0	-4	Slow == Fast → Cycle detected!

Animated walkthrough

How the tortoise and hare detect a cycle

Use Next or Autoplay to see the slow (tortoise) and fast (hare) pointers move through the list. When they meet, a cycle is confirmed.

Back Autoplay Next Reset

Step 1 of 7

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function hasCycle(head):
    if head is null or head.next is null:
        return false

    slow = head
    fast = head

    while fast is not null and fast.next is not null:
        slow = slow.next                    // Move 1 step
        fast = fast.next.next              // Move 2 steps

        if slow == fast:
            return true                     // Collision detected

    return false                            // No cycle found

Solution Code

Python

linked_list_cycle_floyd.py

from typing import Optional


class ListNode:
    def __init__(self, x: int):
        self.val = x
        self.next: Optional['ListNode'] = None


def hasCycle(head: Optional[ListNode]) -> bool:
    if not head or not head.next:
        return False

    slow = head
    fast = head

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

        if slow == fast:
            return True

    return False


# Test cases
if __name__ == "__main__":
    # Test case 1: Cycle exists
    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(f"Cycle exists: {hasCycle(node1)}")  # True

    # Test case 2: No cycle
    node5 = ListNode(1)
    node6 = ListNode(2)
    node5.next = node6
    print(f"Cycle exists: {hasCycle(node5)}")  # False

    # Test case 3: Single node, no cycle
    node7 = ListNode(1)
    print(f"Cycle exists: {hasCycle(node7)}")  # False

C++

linked_list_cycle_floyd.cpp

#include <iostream>
using namespace std;

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

class Solution {
public:
    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;
    }
};

int main() {
    Solution solution;

    // Test case 1: Cycle exists
    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
    cout << "Cycle exists: " << (solution.hasCycle(node1) ? "true" : "false") << endl;  // true

    // Test case 2: No cycle
    ListNode* node5 = new ListNode(1);
    ListNode* node6 = new ListNode(2);
    node5->next = node6;
    cout << "Cycle exists: " << (solution.hasCycle(node5) ? "true" : "false") << endl;  // false

    // Test case 3: Single node
    ListNode* node7 = new ListNode(1);
    cout << "Cycle exists: " << (solution.hasCycle(node7) ? "true" : "false") << endl;  // false

    return 0;
}

Java

linked_list_cycle_floyd.java

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

class Solution {
    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;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();

        // Test case 1: Cycle exists
        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
        System.out.println("Cycle exists: " + solution.hasCycle(node1));  // true

        // Test case 2: No cycle
        ListNode node5 = new ListNode(1);
        ListNode node6 = new ListNode(2);
        node5.next = node6;
        System.out.println("Cycle exists: " + solution.hasCycle(node5));  // false

        // Test case 3: Single node
        ListNode node7 = new ListNode(1);
        System.out.println("Cycle exists: " + solution.hasCycle(node7));  // false
    }
}

JavaScript

linked_list_cycle_floyd.js

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

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    if (!head || !head.next) {
        return false;
    }

    let slow = head;
    let fast = head;

    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;

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

    return false;
};

// Test cases
if (require.main === module) {
    // Test case 1: Cycle exists
    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("Cycle exists:", hasCycle(node1));  // true

    // Test case 2: No cycle
    const node5 = new ListNode(1);
    const node6 = new ListNode(2);
    node5.next = node6;
    console.log("Cycle exists:", hasCycle(node5));  // false

    // Test case 3: Single node
    const node7 = new ListNode(1);
    console.log("Cycle exists:", hasCycle(node7));  // false
}

module.exports = hasCycle;

Rust

linked_list_cycle_floyd.rs

use std::collections::VecDeque;

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    #[inline]
    fn new(val: i32) -> Self {
        ListNode { next: None, val }
    }
}

struct Solution;

impl Solution {
    pub fn has_cycle(head: Option<Box<ListNode>>) -> bool {
        let mut slow = head.clone();
        let mut fast = head;

        while let Some(fast_node) = fast {
            // Move fast pointer twice
            fast = fast_node.next.clone();
            if let Some(fast_node2) = fast {
                fast = fast_node2.next.clone();
            } else {
                return false;
            }

            // Move slow pointer once
            if let Some(slow_node) = slow {
                slow = slow_node.next.clone();
            } else {
                return false;
            }

            // Check if they point to the same node
            if slow == fast {
                return true;
            }
        }

        false
    }
}

fn main() {
    // Test case 1: Cycle exists
    let mut node1 = Box::new(ListNode::new(3));
    let mut node2 = Box::new(ListNode::new(2));
    let mut node3 = Box::new(ListNode::new(0));
    let node4 = Box::new(ListNode::new(-4));

    node3.next = Some(node4);
    node2.next = Some(node3);
    node1.next = Some(node2);
    // Note: Cannot create actual cycle with Rust's ownership model in this simple example

    println!("Linked List Cycle - Floyd's Algorithm");
}

Go

linked_list_cycle_floyd.go

package main

import "fmt"

type ListNodeFloyd struct {
  Val  int
  Next *ListNodeFloyd
}

func hasCycleFloyd(head *ListNodeFloyd) bool {
  if head == nil || head.Next == nil {
    return false
  }

  slow := head
  fast := head

  for fast != nil && fast.Next != nil {
    slow = slow.Next
    fast = fast.Next.Next

    if slow == fast {
      return true
    }
  }

  return false
}

func mainFloyd() {
  // Test case 1: Cycle exists
  node1 := &ListNodeFloyd{Val: 3}
  node2 := &ListNodeFloyd{Val: 2}
  node3 := &ListNodeFloyd{Val: 0}
  node4 := &ListNodeFloyd{Val: -4}
  node1.Next = node2
  node2.Next = node3
  node3.Next = node4
  node4.Next = node2  // Cycle

  fmt.Println("Cycle exists:", hasCycleFloyd(node1))  // true

  // Test case 2: No cycle
  node5 := &ListNodeFloyd{Val: 1}
  node6 := &ListNodeFloyd{Val: 2}
  node5.Next = node6
  fmt.Println("Cycle exists:", hasCycleFloyd(node5))  // false

  // Test case 3: Single node
  node7 := &ListNodeFloyd{Val: 1}
  fmt.Println("Cycle exists:", hasCycleFloyd(node7))  // false
}

Approach 2: Hash Set

✓ Simple

Iterate through the linked list, storing each visited node in a set. If we encounter a node that is already in the set, a cycle exists. If we reach the end of the list (null), there is no cycle.

⏱ Time O(n) Single pass through list 💾 Space O(n) Set grows with visited nodes

Step-by-step Example

Input: [3, 2, 0, -4] with cycle at index 1

Node	In Set?	Action
3	No	Add to set → {3}
2	No	Add to set → {3, 2}
0	No	Add to set → {3, 2, 0}
-4	No	Add to set → {3, 2, 0, -4}
2	Yes	Cycle detected! Return true

Pseudocode

function hasCycle(head):
    seen = empty set
    current = head

    while current is not null:
        if current is in seen:
            return true                     // Found a cycle
        seen.add(current)
        current = current.next

    return false                            // No cycle found

Solution Code

Python

linked_list_cycle_hash_set.py

from typing import Optional


class ListNode:
    def __init__(self, x: int):
        self.val = x
        self.next: Optional['ListNode'] = None


def hasCycle(head: Optional[ListNode]) -> bool:
    seen = set()
    current = head

    while current:
        if current in seen:
            return True
        seen.add(current)
        current = current.next

    return False


# Test cases
if __name__ == "__main__":
    # Test case 1: Cycle exists
    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(f"Cycle exists: {hasCycle(node1)}")  # True

    # Test case 2: No cycle
    node5 = ListNode(1)
    node6 = ListNode(2)
    node5.next = node6
    print(f"Cycle exists: {hasCycle(node5)}")  # False

    # Test case 3: Single node, no cycle
    node7 = ListNode(1)
    print(f"Cycle exists: {hasCycle(node7)}")  # False

C++

linked_list_cycle_hash_set.cpp

#include <iostream>
#include <unordered_set>
using namespace std;

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

class Solution {
public:
    bool hasCycle(ListNode* head) {
        unordered_set<ListNode*> seen;
        ListNode* current = head;

        while (current) {
            if (seen.count(current)) {
                return true;
            }
            seen.insert(current);
            current = current->next;
        }

        return false;
    }
};

int main() {
    Solution solution;

    // Test case 1: Cycle exists
    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
    cout << "Cycle exists: " << (solution.hasCycle(node1) ? "true" : "false") << endl;  // true

    // Test case 2: No cycle
    ListNode* node5 = new ListNode(1);
    ListNode* node6 = new ListNode(2);
    node5->next = node6;
    cout << "Cycle exists: " << (solution.hasCycle(node5) ? "true" : "false") << endl;  // false

    // Test case 3: Single node
    ListNode* node7 = new ListNode(1);
    cout << "Cycle exists: " << (solution.hasCycle(node7) ? "true" : "false") << endl;  // false

    return 0;
}

Java

linked_list_cycle_hash_set.java

import java.util.HashSet;
import java.util.Set;

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> seen = new HashSet<>();
        ListNode current = head;

        while (current != null) {
            if (seen.contains(current)) {
                return true;
            }
            seen.add(current);
            current = current.next;
        }

        return false;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();

        // Test case 1: Cycle exists
        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
        System.out.println("Cycle exists: " + solution.hasCycle(node1));  // true

        // Test case 2: No cycle
        ListNode node5 = new ListNode(1);
        ListNode node6 = new ListNode(2);
        node5.next = node6;
        System.out.println("Cycle exists: " + solution.hasCycle(node5));  // false

        // Test case 3: Single node
        ListNode node7 = new ListNode(1);
        System.out.println("Cycle exists: " + solution.hasCycle(node7));  // false
    }
}

JavaScript

linked_list_cycle_hash_set.js

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

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    const seen = new Set();
    let current = head;

    while (current) {
        if (seen.has(current)) {
            return true;
        }
        seen.add(current);
        current = current.next;
    }

    return false;
};

// Test cases
if (require.main === module) {
    // Test case 1: Cycle exists
    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("Cycle exists:", hasCycle(node1));  // true

    // Test case 2: No cycle
    const node5 = new ListNode(1);
    const node6 = new ListNode(2);
    node5.next = node6;
    console.log("Cycle exists:", hasCycle(node5));  // false

    // Test case 3: Single node
    const node7 = new ListNode(1);
    console.log("Cycle exists:", hasCycle(node7));  // false
}

module.exports = hasCycle;

Rust

linked_list_cycle_hash_set.rs

use std::collections::HashSet;

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    #[inline]
    fn new(val: i32) -> Self {
        ListNode { next: None, val }
    }
}

struct Solution;

impl Solution {
    pub fn has_cycle(head: Option<Box<ListNode>>) -> bool {
        let mut seen = HashSet::new();
        let mut current = head;

        while let Some(node) = current {
            let node_ptr = &node as *const _;
            if !seen.insert(node_ptr as usize) {
                return true;
            }
            current = node.next;
        }

        false
    }
}

fn main() {
    // Test case: Basic structure without cycle
    let node1 = Box::new(ListNode::new(1));
    let mut node2 = Box::new(ListNode::new(2));
    node2.next = None;

    let mut node3 = Box::new(ListNode::new(3));
    node3.next = Some(node2);

    println!("Linked List Cycle - Hash Set Approach");
}

Go

linked_list_cycle_hash_set.go

package main

import "fmt"

type ListNodeHash struct {
  Val  int
  Next *ListNodeHash
}

func hasCycleHash(head *ListNodeHash) bool {
  seen := make(map[*ListNodeHash]bool)
  current := head

  for current != nil {
    if seen[current] {
      return true
    }
    seen[current] = true
    current = current.Next
  }

  return false
}

func mainHash() {
  // Test case 1: Cycle exists
  node1 := &ListNodeHash{Val: 3}
  node2 := &ListNodeHash{Val: 2}
  node3 := &ListNodeHash{Val: 0}
  node4 := &ListNodeHash{Val: -4}
  node1.Next = node2
  node2.Next = node3
  node3.Next = node4
  node4.Next = node2  // Cycle

  fmt.Println("Cycle exists:", hasCycleHash(node1))  // true

  // Test case 2: No cycle
  node5 := &ListNodeHash{Val: 1}
  node6 := &ListNodeHash{Val: 2}
  node5.Next = node6
  fmt.Println("Cycle exists:", hasCycleHash(node5))  // false

  // Test case 3: Single node
  node7 := &ListNodeHash{Val: 1}
  fmt.Println("Cycle exists:", hasCycleHash(node7))  // false
}

Watch for these pitfalls

• Null pointer checks: Always check if head is null or head.next is null before entering the loop in Floyd’s algorithm.
• Fast pointer safety: In Floyd’s algorithm, check that fast and fast.next are not null before advancing; otherwise, you risk a null pointer exception.
• Hash set memory: The hash set approach uses O(n) extra space, which can be problematic for very large lists.
• Pointer identity vs. value: Use pointer comparison (==), not value comparison, to detect cycles. Two different nodes with the same value are not the same node.

Approach 3: Optimized Two-Pointer

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

linked_list_cycle_optimized.py

"""
Solution for Linked List Cycle
"""

def solve():
    """Implementation for approach 3 of Linked List Cycle"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

linked_list_cycle_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Linked List Cycle
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

LinkedListCycleOptimized.java

/**
 * Solution for Linked List Cycle
 * Approach 3
 */
public class LinkedListCycleOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

linked_list_cycle_optimized.js

/**
 * Solution for Linked List Cycle
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

linked_list_cycle_optimized.rs

/// Solution for Linked List Cycle
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

linked_list_cycle_optimized.go

package main

import "fmt"

// Solution for Linked List Cycle
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Add Two Numbers Medium #2
• Linked List Cycle II ↗ Medium #142
• Intersection of Two Linked Lists ↗ Easy #160
• Reverse Linked List ↗ Easy #206

Interview Tips

Key trade-offs to discuss

• Why Floyd’s Algorithm? It is O(1) space and demonstrates sophisticated two-pointer technique. This is the expected solution for optimal interviews.
• Hash Set alternative: If you struggle to recall Floyd’s algorithm, the hash set approach is correct and O(n) space is often acceptable.
• Proof of correctness: Floyd’s algorithm works because in a circular list, the difference in speeds guarantees eventual collision. The relative speed of 2 vs. 1 means the fast pointer “laps” the slow pointer.
• Edge cases: Empty list, single node, two-node cycle, and late-cycle entry all test your implementation thoroughly.
• Follow-up: Problem #142 asks for the cycle start node — Floyd’s algorithm can be extended to find it in two phases.

← Previous
#139 Word Break Next
#146 LRU Cache →