LeetCode 141 - Linked List Cycle

2026-07-13

easy　linked list　hash set　two pointers

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

A cycle exists if some node can be reached again by continuously following next pointers. pos denotes the index the tail connects back to — it is not passed as a parameter.

Return true if there is a cycle, false otherwise.

Example 1:

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

Output: true

Explanation: The tail connects back to index 1, forming a cycle.

Example 2:

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

Output: true

Explanation: The tail connects back to index 0, forming a cycle.

Example 3:

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

Output: false

Explanation: No cycle — the list ends normally.

Constraints:

• 0 <= number of nodes <= 10,000
• -100,000 <= Node.val <= 100,000
• pos is -1 or a valid index in the list.

Solution 1:

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        # Approach: Hash Set of Visited Nodes
        # 1. Traverse the list, storing each node object (not its value) in a set.
        # 2. Before adding a node, check if it's already in the set.
        #    If yes, we've visited it before — a cycle exists, return True.
        # 3. If we reach None, the list has a proper end — no cycle, return False.
        # Note: we store node references, not values, since different nodes can share values.
        # Time Complexity: O(N) — each node is visited at most once.
        # Space Complexity: O(N) — the set holds up to N node references.
        cur_seen = set()
        cur = head
        while cur:
            if cur in cur_seen:
                return True
            cur_seen.add(cur)
            cur = cur.next
        return False

Solution 2:

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        # Approach: Floyd's Cycle Detection (Tortoise and Hare)
        # Use two pointers starting at head:
        #   slow (idx1) — advances one step at a time.
        #   fast (idx2) — advances two steps at a time.
        # If there is no cycle, fast will reach None and the loop exits — return False.
        # If there is a cycle, fast laps slow and they eventually meet — return True.
        # The loop condition checks both idx2 and idx2.next to safely call idx2.next.next.
        # Time Complexity: O(N) — fast catches slow within one full loop of the cycle.
        # Space Complexity: O(1) — only two pointers, no extra storage.
        idx1 = head
        idx2 = head

        while idx2 and idx2.next:
            idx1 = idx1.next
            idx2 = idx2.next.next
            if idx2 == idx1:
                return True
        return False

Conclusion

Today we detected a linked list cycle two ways.

Solution 1 uses a hash set to remember every node we've visited. If we ever encounter a node that's already in the set, we've looped back — cycle confirmed. Simple and correct, but it costs O(N) extra space.

Solution 2 is Floyd's Cycle Detection algorithm — also known as the tortoise and hare. A slow pointer moves one step at a time while a fast pointer moves two. If the list has no cycle, fast hits None and we exit. If there is a cycle, fast eventually laps slow inside the loop and they collide. The two pointers are guaranteed to meet because fast gains exactly one step on slow per iteration, so within at most one full cycle length, they converge.

The O(1) space makes Solution 2 the preferred answer in interviews. The tortoise-and-hare pattern also extends naturally to LeetCode 142 (finding the exact entry point of the cycle) — worth knowing as a follow-up.