Linked List Cycle

easy
Linked ListLinked ListTwo Pointers

Given head, the head of a linked list, determine if the linked list has a cycle in it. A cycle exists when a node in the list can be reached again by continuously following the next pointer.

Internally, pos is used to denote the index of the node that the 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.

Examples

Example 1

  • Input: head = [3,2,0,-4], pos = 1
  • Output: true
  • Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2

  • Input: head = [1,2], pos = 0
  • Output: true
  • Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3

  • Input: head = [1], pos = -1
  • Output: false
  • Explanation: There is no cycle in the linked list.

Constraints

  • The number of 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.

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Hash Set

Intuition

The most straightforward way to detect a cycle is to keep track of every node we have visited. As we traverse the list, we check whether the current node has been seen before. If we encounter a previously visited node, a cycle exists. If we reach the end of the list (null), there is no cycle. This approach trades space for simplicity.

Algorithm

  1. Create an empty hash set to store visited node references.
  2. Start at `head` and traverse the list.
  3. For each node, check if it already exists in the set.
  4. If it does, return `true` (cycle detected).
  5. Otherwise, add the node to the set and move to the next node.
  6. If the traversal reaches null, return `false`.
TimeO(n)SpaceO(n)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode*> visited;
        ListNode* curr = head;

        while (curr != nullptr) {
            if (visited.count(curr)) {
                return true;
            }
            visited.insert(curr);
            curr = curr->next;
        }

        return false;
    }
};
Java 21
class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> visited = new HashSet<>();
        ListNode curr = head;

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

        return false;
    }
}
Python 3.12
def hasCycle(head: Optional[ListNode]) -> bool:
    visited = set()
    curr = head

    while curr:
        if curr in visited:
            return True
        visited.add(curr)
        curr = curr.next

    return False
Go 1.26
func hasCycle(head *ListNode) bool {
    visited := map[*ListNode]bool{}
    curr := head

    for curr != nil {
        if visited[curr] {
            return true
        }
        visited[curr] = true
        curr = curr.Next
    }

    return false
}
Approach 2

Floyd's Tortoise and Hare

Intuition

Floyd's cycle detection algorithm uses two pointers moving at different speeds. The slow pointer moves one step at a time while the fast pointer moves two steps. If there is a cycle, the fast pointer will eventually lap the slow pointer and they will meet inside the cycle. If there is no cycle, the fast pointer will reach the end of the list. This is the optimal approach because it uses constant extra space.

Algorithm

  1. Initialize two pointers, `slow` and `fast`, both starting at `head`.
  2. Move `slow` one step forward and `fast` two steps forward in each iteration.
  3. If `fast` or `fast.next` becomes null, there is no cycle -- return `false`.
  4. If `slow` and `fast` meet (point to the same node), a cycle exists -- return `true`.
TimeO(n)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
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;
    }
};
Java 21
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;
    }
}
Python 3.12
def hasCycle(head: Optional[ListNode]) -> bool:
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True

    return False
Go 1.26
func hasCycle(head *ListNode) bool {
    slow := head
    fast := head

    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            return true
        }
    }

    return false
}

Frequently asked questions

What is the optimal time complexity of Linked List Cycle?

The most efficient approach in this guide ("Floyd's Tortoise and Hare") runs in O(n) time and uses O(1) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Linked List Cycle use?

Linked List Cycle is a easy-level Linked List problem involving Linked List, Two Pointers. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Linked List Cycle be solved without extra space?

The most space-efficient approach in this guide uses O(1) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(n), while the optimized version uses O(1).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Original problem: leetcode.com

Loading editor...
Input
head=
[[3,2,0,-4],1]
Expected Output
true