Linked List Cycle

Difficulty: Easy

Problem

You are given the head of a singly linked list. Work out whether following next pointers from the head can ever loop back to a node you have already visited.

In the examples, pos is the index of the node that the tail's next pointer attaches to (it is -1 when there is no loop). It only describes how the test was built and is not passed to your function.

Return true if the list contains a loop, otherwise false.

Example

Input: head = [1,5,8,2], pos = 0
Output: true
Explanation: The tail (value 2) points back to the node at index 0, so walking forward never ends: there is a cycle.

Brute-force approach, Using a Hash Set to Track Visited Nodes

Visit each node and store it in a hash set. If we encounter a node that is already in the set, we've found a cycle. If we reach null, there is no cycle.

Steps

  1. Create an empty hash set to track visited nodes
  2. Traverse the linked list from head
  3. For each node, check if it exists in the set
  4. If found → cycle detected, return true
  5. If not found → add it to the set and move to next
  6. If we reach null → no cycle, return false

Time complexity: O(n) · Space complexity: O(n)

Trade-offs

  • Uses O(n) extra space for the hash set
  • Hash operations add overhead compared to pointer manipulation

Optimal approach, Floyd's Tortoise and Hare Algorithm

Key insight: If two pointers move at different speeds inside a cycle, the faster one will eventually catch up to the slower one.

Use two pointers: a slow pointer that moves one step at a time and a fast pointer that moves two steps. If there's a cycle, they will eventually meet. If there's no cycle, the fast pointer will reach the end.

Steps

  1. Initialize slow and fast pointers at head
  2. Move slow one step, fast two steps
  3. If slow == fast → cycle found, return true
  4. If fast reaches null → no cycle, return false

Time complexity: O(n) · Space complexity: O(1)

Pseudocode

function hasCycle(head):
    slow = head
    fast = head
    while fast != null AND fast.next != null:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return true
    return false

Hints

  • Use two pointers moving at different speeds
  • If there's a cycle, the fast pointer will eventually meet the slow pointer
  • If there's no cycle, the fast pointer will reach the end

Complexity questions

What is the time complexity of the hash set approach?

O(n). We visit each node at most once, giving O(n) time.

What is the space complexity of the hash set approach?

O(n). We store up to n nodes in the hash set, giving O(n) space.

What is the time complexity of Floyd's algorithm?

O(n). The slow pointer traverses at most n + C nodes where C is the cycle length, so it's O(n).

What is the space complexity of Floyd's algorithm?

O(1). Floyd's algorithm uses only two pointers regardless of input size, giving O(1) space.

Check your understanding of Linked List Cycle

What defines a cycle in a linked list?

A node whose next pointer points to a previously visited node. A cycle exists when a node's next pointer points back to a node that was already visited, creating an infinite loop.

In the list 1 → 2 → 3 → 4 → 2 (back to node 2), does a cycle exist?

Yes, because node 4's next points back to node 2, creating a loop. A cycle exists because traversing from node 4 leads back to node 2, creating an infinite loop: 2 → 3 → 4 → 2 → 3 → ... Cycles depend on pointer connections, not values.

Can a single node (1 → null) have a cycle?

No, because its next pointer is null — there's no loop back. A single node pointing to null has no cycle. A cycle requires a node's next pointer to eventually lead back to a previously visited node. If next is null, traversal simply ends.

Related problems

Keep practising