Linked List Cycle

Problem Description

Given head, 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.

Examples

Constraints

• The number of nodes in the list is in the range [0, 10⁴].
• -10⁵ ≤ Node.val ≤ 10⁵
• pos is -1 or a valid index in the linked-list.

The Speed Difference Makes Loop Iteration Converge

The simple way to find a cycle is tracking nodes in a hash set. This costs O(n) space. To achieve O(1) space, we use two pointers moving at different speeds. This is Floyd’s Cycle-Finding algorithm.

Think of it like two runners on a track. If the track is a straight line, the faster runner reaches the end first. If the track is a circular loop, the faster runner eventually laps the slower runner. By moving a slow pointer by one step and a fast pointer by two steps, they will always meet if a cycle exists.

Solution 1: Hash Set Lookup

Store visited nodes in a hash set. If you encounter a node that is already in the set, a cycle exists.

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

public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> visited = new HashSet<>();
        ListNode curr = head;
        while (curr != null) {
            // if node already exists in set, we found a cycle
            if (!visited.add(curr)) {
                return true;
            }
            curr = curr.next;
        }
        return false;
    }
}

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        visited = set()
        curr = head
        while curr:
            # if node already exists in set, we found a cycle
            if curr in visited:
                return True
            visited.add(curr)
            curr = curr.next
        return False

#include <unordered_set>

class Solution {
public:
    bool hasCycle(ListNode *head) {
        std::unordered_set<ListNode*> visited;
        ListNode* curr = head;
        while (curr) {
            // if node already exists in set, we found a cycle
            if (visited.count(curr)) {
                return true;
            }
            visited.insert(curr);
            curr = curr->next;
        }
        return false;
    }
};

Complexity Analysis:

• Time Complexity: O(n) where n is the number of nodes in the linked list.
• Space Complexity: O(n) to store the visited nodes in the set.

Where it breaks: If the list is large, the memory allocated for the set can become a constraint. This solution fails if you are restricted to constant space.

Solution 2: Floyd’s Cycle-Finding Algorithm (Two Pointers)

Use a slow pointer that moves one step and a fast pointer that moves two steps. If they meet, there is a cycle. If fast reaches null, there is no cycle.

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) return false;
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;        // moves 1 step
            fast = fast.next.next;   // moves 2 steps
            if (slow == fast) {
                return true;         // fast caught up to slow, cycle detected
            }
        }
        return false;
    }
}

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next          # moves 1 step
            fast = fast.next.next     # moves 2 steps
            if slow == fast:
                return True           # fast caught up to slow, cycle detected
        return False

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next) {
            slow = slow->next;        // moves 1 step
            fast = fast->next->next;  // moves 2 steps
            if (slow == fast) {
                return true;          // fast caught up to slow, cycle detected
            }
        }
        return false;
    }
};

Complexity Analysis:

• Time Complexity: O(n). If no cycle exists, fast reaches the end in n/2 steps. If a cycle exists, the distance between slow and fast decreases by one each step, converging within one loop traversal.
• Space Complexity: O(1) as we only use two pointer variables.

Where it breaks: This algorithm only detects the presence of a cycle. If you need to find the exact node where the cycle begins (like in LeetCode 142), you need an extra phase to reset one pointer to the head and move both at a speed of one step until they meet again.

Common Mistakes

• Dereferencing null pointer on fast check. You must check both fast and fast.next in your loop condition before accessing fast.next.next.
• Comparing node values instead of node references. Different nodes can have the exact same value. You must check if the pointers refer to the same object in memory.
• Not handling the single-node base cases. An empty list or a list with only one node without a loop should return false immediately.

Frequently Asked Questions

Why does the fast pointer only move two steps? Can it move three? If fast moves three steps, it might jump over slow without landing on the same node, which complicates cycle detection. Moving two steps ensures the gap decreases by exactly one each loop iteration, guarantees they will meet.

What if the tail points back to the head? Floyd’s algorithm handles this. The pointers will loop through the entire list and meet at some node in O(n) time.

What does this problem test in interviews? It tests your knowledge of pointer operations, basic linked list traversal, and your ability to optimize space from linear to constant.

← All Problems