Linked List Cycle

Difficulty: Easy

Problem

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

A cycle exists if some node in the list can be reached again by continuously following the next pointer. Internally, pos denotes the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

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)