Skip to main content
CodePeetCodePeet
BLIND 75

Linked List Cycle

EASYProblemSolveExternal Links

Description

You are given the head of a singly linked list. Your task is to determine whether the linked list contains a cycle.

A cycle exists in a linked list when some node's next pointer points back to a previously visited node, instead of pointing to null. This means if you keep following next pointers, you will loop forever and never reach the end of the list.

Internally, the variable pos indicates the index (0-based) of the node that the tail's next pointer connects to. However, pos is not passed as a parameter to your function — it is only used to construct the test case.

Return true if there is a cycle in the linked list, and false otherwise.

Examples

Example 1

Input: head = [3, 2, 0, -4], pos = 1

Output: true

Explanation: The linked list has 4 nodes with values 3 → 2 → 0 → -4. The last node (-4) connects back to the node at index 1 (value 2), forming a cycle. If you traverse the list, you will visit 3 → 2 → 0 → -4 → 2 → 0 → -4 → 2 → ... endlessly. A cycle exists, so we return true.

Example 2

Input: head = [1, 2], pos = 0

Output: true

Explanation: The list has 2 nodes: 1 → 2. The tail node (value 2) connects back to the node at index 0 (value 1), creating a cycle: 1 → 2 → 1 → 2 → ... Therefore, we return true.

Example 3

Input: head = [1], pos = -1

Output: false

Explanation: The list has a single node with value 1, and its next pointer is null. There is no cycle because no node loops back to a previous node. We return false.

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

Editorial

Brute Force

Intuition

The most natural way to detect a cycle is to keep track of every node we have visited. As we traverse the linked list, we check: "Have I seen this node before?" If yes, we have found a cycle. If we reach a null pointer (the end of the list) without ever revisiting a node, then there is no cycle.

Think of it like walking through a trail in a forest and leaving breadcrumbs at each intersection. If you ever arrive at a spot where breadcrumbs already exist, you know you have been going in circles. If you reach a dead end with no prior breadcrumbs, the trail has no loops.

We can use a hash set to store references to every node we visit. A hash set allows us to check whether a node has been seen before in O(1) average time.

Step-by-Step Explanation

Let's trace through with head = [3, 2, 0, -4], pos = 1 (tail connects back to node at index 1):

Step 1: Initialize an empty hash set. Start at the head node (value 3).

Step 2: Is node(3) in the set? No (set is empty). Add node(3) to the set. Set: {node(3)}. Move to next: node(2).

Step 3: Is node(2) in the set? No. Add node(2). Set: {node(3), node(2)}. Move to next: node(0).

Step 4: Is node(0) in the set? No. Add node(0). Set: {node(3), node(2), node(0)}. Move to next: node(-4).

Step 5: Is node(-4) in the set? No. Add node(-4). Set: {node(3), node(2), node(0), node(-4)}. Move to next: the tail's next points back to node(2).

Step 6: Is node(2) in the set? YES! We have visited node(2) before (at step 3). This means we've entered a cycle. Return true.

Linked List Cycle Detection — Hash Set Approach — Watch how we traverse the linked list while recording each visited node in a set. When we encounter a node already in the set, a cycle is detected.

Algorithm

  1. Create an empty hash set to store visited node references
  2. Start at the head node
  3. While the current node is not null:
    • If the current node is already in the set, return true (cycle detected)
    • Add the current node to the set
    • Move to the next node
  4. If we exit the loop (reached null), return false (no cycle)

Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode*> visited;
        
        ListNode* current = head;
        while (current != nullptr) {
            // If this node was already visited, cycle exists
            if (visited.count(current)) {
                return true;
            }
            visited.insert(current);
            current = current->next;
        }
        
        // Reached end of list, no cycle
        return false;
    }
};
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        visited = set()
        
        current = head
        while current is not None:
            # If we've seen this node before, there's a cycle
            if current in visited:
                return True
            visited.add(current)
            current = current.next
        
        # Reached the end, no cycle
        return False
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> visited = new HashSet<>();
        
        ListNode current = head;
        while (current != null) {
            // If already in set, cycle detected
            if (visited.contains(current)) {
                return true;
            }
            visited.add(current);
            current = current.next;
        }
        
        // Reached end of list
        return false;
    }
}

Complexity Analysis

Time Complexity: O(n)

We visit each node at most once before either detecting the cycle or reaching the end of the list. Each hash set operation (insertion and lookup) takes O(1) on average. With n nodes, the total time is O(n).

Space Complexity: O(n)

In the worst case (no cycle), we store all n nodes in the hash set before reaching the end. The space used grows linearly with the number of nodes.

Why This Approach Is Not Efficient

The hash set approach correctly detects cycles in O(n) time, which is already optimal — we must visit each node at least once to determine if a cycle exists. However, it uses O(n) extra space to store the visited nodes.

With up to 10^4 nodes, the space is manageable but still unnecessary. The problem's follow-up explicitly asks: "Can you solve it using O(1) memory?"

The key insight is that we don't need to remember every node we've visited. Instead, we can use a clever two-pointer technique where two pointers move at different speeds. If there's a cycle, the faster pointer will eventually "lap" the slower one — like two runners on a circular track. This eliminates the need for any extra data structure.

Optimal Approach - Floyd's Cycle Detection (Tortoise and Hare)

Intuition

Imagine two runners on a track. One runs at normal speed (the "tortoise"), and the other runs at double speed (the "hare"). If the track is a straight line with an end, the hare will reach the end first and we'll know there's no loop. But if the track forms a loop, the hare will eventually come around and meet the tortoise from behind — they will be on the same spot at the same time.

This is the core idea behind Floyd's Cycle Detection Algorithm. We use two pointers:

  • slow moves one step at a time
  • fast moves two steps at a time

Both start at the head. If there is no cycle, the fast pointer will reach null (end of list), and we return false. If there IS a cycle, the fast pointer enters the cycle first and starts going around it. The slow pointer eventually enters the cycle too. Once both are inside the cycle, the fast pointer gains one position on the slow pointer each iteration (since it moves 2 steps vs 1 step). This means the gap between them decreases by 1 each step, and they are guaranteed to meet.

The beauty of this approach is that it uses only two pointer variables — O(1) space.

Step-by-Step Explanation

Let's trace with head = [3, 2, 0, -4], pos = 1 (tail connects to node at index 1):

Nodes: index 0 (val 3) → index 1 (val 2) → index 2 (val 0) → index 3 (val -4) → back to index 1.

Step 1: Initialize slow = head (index 0), fast = head (index 0). Both start at node with value 3.

Step 2: Move slow one step: slow = node at index 1 (val 2). Move fast two steps: fast goes from index 0 → index 1 → index 2 (val 0). Are slow and fast the same node? slow is at index 1, fast is at index 2. Not equal.

Step 3: Move slow one step: slow = node at index 2 (val 0). Move fast two steps: fast goes from index 2 → index 3 → index 1 (val 2, via the cycle link). Are slow and fast the same node? slow is at index 2, fast is at index 1. Not equal.

Step 4: Move slow one step: slow = node at index 3 (val -4). Move fast two steps: fast goes from index 1 → index 2 → index 3 (val -4). Are slow and fast the same node? slow is at index 3, fast is at index 3. They are the same node!

Step 5: Return true. The pointers met, confirming a cycle exists.

Floyd's Cycle Detection — Tortoise and Hare on [3, 2, 0, -4] — Watch the slow pointer (tortoise) move one step and the fast pointer (hare) move two steps each iteration. When they meet inside the cycle, a cycle is confirmed.

Algorithm

  1. If the list is empty (head is null), return false
  2. Initialize two pointers: slow = head, fast = head
  3. While fast is not null AND fast.next is not null:
    • Move slow one step forward: slow = slow.next
    • Move fast two steps forward: fast = fast.next.next
    • If slow == fast, return true (cycle detected)
  4. If the loop exits (fast reached null), return false (no cycle)

Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;          // Move one step
            fast = fast->next->next;    // Move two steps
            
            if (slow == fast) {
                return true;            // Pointers met — cycle!
            }
        }
        
        // Fast reached the end — no cycle
        return false;
    }
};
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = head
        fast = head
        
        while fast is not None and fast.next is not None:
            slow = slow.next          # One step
            fast = fast.next.next     # Two steps
            
            if slow == fast:
                return True           # Met — cycle exists
        
        # Fast reached end — no cycle
        return False
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         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;          // One step
            fast = fast.next.next;     // Two steps
            
            if (slow == fast) {
                return true;           // Cycle detected
            }
        }
        
        // Reached end of list
        return false;
    }
}

Complexity Analysis

Time Complexity: O(n)

If there is no cycle, the fast pointer reaches the end in n/2 iterations, giving O(n). If there is a cycle, let m be the number of nodes before the cycle and c be the cycle length. Once the slow pointer enters the cycle, the fast pointer is at most c steps ahead in the cycle. Since the gap closes by 1 each iteration, they meet within at most c iterations after slow enters the cycle. Total: O(m + c) = O(n).

Space Complexity: O(1)

We use only two pointer variables (slow and fast), regardless of the size of the linked list. No additional data structures are needed, making this solution truly constant-space.