Linked List Cycle

Given the beginning of a linked list head, return true if there is a cycle in the linked list. Otherwise, return false.

A cycle exists if at least one node in the list can be visited again by following next pointers. Internally, index is the 0-based index of the node the tail connects back to. If index = -1, the tail points to null and no cycle exists.

Examples

• 0 ≤ length of list ≤ 1000
• -1000 ≤ Node.val ≤ 1000
• index is -1 or a valid index in the linked list.

Prerequisites

Before attempting this problem, you should be comfortable with:

• Linked Lists — traversing nodes using next pointers
• Hash Sets — O(1) insertion and lookup to track visited nodes
• Fast and Slow Pointers (Floyd's Algorithm) — two-pointer technique for cycle detection with O(1) space

1. Hash Set

Intuition

Track every node visited so far in a hash set. As we traverse the list, if we ever reach a node already in the set, we've come back to a node we saw before — a cycle exists. If we reach null without repeating any node, there is no cycle.

Algorithm

• Create an empty hash set seen. Set cur = head.
• While cur is not null:
• If cur is already in seen, return true.
• Add cur to seen. Advance cur = cur.next.
• Return false.

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        seen = set()
        cur = head
        while cur:
            if cur in seen:
                return True
            seen.add(cur)
            cur = cur.next
        return False

class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> seen = new HashSet<>();
        ListNode cur = head;
        while (cur != null) {
            if (seen.contains(cur)) return true;
            seen.add(cur);
            cur = cur.next;
        }
        return false;
    }
}

Time Complexity: O(n) — each node visited at most once.
Space Complexity: O(n) — hash set stores up to n node references.

2. Fast and Slow Pointers (Floyd's Cycle Detection)

Intuition

Use two pointers starting at head: slow moves one step at a time, fast moves two steps at a time. If there is no cycle, fast will reach the end. If there is a cycle, fast will eventually "lap" slow — they will meet at the same node inside the cycle.

Think of it like two runners on a circular track: the faster one will eventually catch up to the slower one. This requires O(1) space — no extra data structure needed.

Algorithm

• Initialize slow = head, fast = head.
• While fast and fast.next are not null:
• Advance slow = slow.next (one step).
• Advance fast = fast.next.next (two steps).
• If slow == fast, return true (cycle found).
• Return false (fast reached the end).

Common Pitfalls

Not Checking fast.next Before Advancing

Before moving fast two steps, both fast and fast.next must be non-null. Checking only fast != null causes a null pointer exception when fast is at the last node — accessing fast.next.next dereferences a null fast.next.

# Wrong — only checks fast, not fast.next:
while fast:
    fast = fast.next.next  # crashes if fast.next is None!

# Correct — both must be non-null:
while fast and fast.next:
    fast = fast.next.next

Comparing Node Values Instead of Node References

Cycle detection requires slow == fast to compare node identity (same object in memory), not value equality. Using slow.val == fast.val incorrectly triggers on two distinct nodes that happen to have the same value, producing false positives.

Starting fast One Step Ahead

Both pointers must start at head. If fast starts at head.next, the initial positions are offset and the meeting condition may never trigger in a small cycle, or the loop condition fails prematurely on a one-node list.

Hash Set Stores Values Instead of Node References

In the hash set approach, you must store node objects (references/pointers), not their values. Storing values causes false cycle detection when duplicate values appear in an acyclic list. In Python, seen.add(cur) stores the node object; seen.add(cur.val) is wrong.