How do you solve Linked List Cycle Detection?

Initialize two pointers at the head. Move slow by one node and fast by two nodes in each iteration. If at any point slow equals fast, return true indicating a cycle. If fast or fast.next becomes null, return false indicating no cycle.

Linked List Cycle Detection

Q: What is the time complexity of Linked List Cycle Detection?

O(n). Each pointer traverses the list at most once. The fast pointer moves through nodes twice as fast, so the meeting occurs in linear time relative to the list length.

Q: What pattern does Linked List Cycle Detection use?

The Pattern: Fast & Slow Pointers (Cycle Detection in Linked List) The Heuristic: When detecting cycles in linked structures, use two pointers moving at different speeds; if a cycle exists, the faster pointer will eventually catch up to the slower one inside the cycle.

Easy Fast & Slow Pointers

Problem

Given the head of a linked list, determine if the linked list contains a cycle. Return true if there is a cycle in the linked list, otherwise return false.

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

Example

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

Output: true

The linked list contains a cycle because the tail connects to the node at position 1 (0-indexed). The algorithm uses two pointers starting at the head: 'slow' moves one step at a time, 'fast' moves two steps. Initially, both point to the node with value 3. After the first iteration, slow points to 2, fast points to 0. After the second iteration, slow points to 0, fast points to 2. Eventually, slow and fast meet at the node with value 2, confirming a cycle.

Approach

Straightforward Solution

A brute-force approach uses a hash set to record visited nodes and checks for repeats. This requires O(n) space and is less efficient.

Core Observation

If a linked list contains a cycle, two pointers moving at different speeds will eventually meet inside the cycle. If no cycle exists, the fast pointer will reach the end of the list (null) without meeting the slow pointer.

Path to Optimal

Preview

The key recognition signals are 'detect cycle' and 'linked list traversal'. These indicate the Fast & Slow Pointers pattern because it uses two pointers moving at different speeds to detect cycles in O(1) space…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Initialize two pointers at the head. Move slow by one node and fast by two nodes in each iteration…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each pointer traverses the list at most once. The fast pointer moves through nodes twice as fast, so the meeting occurs in linear time relative to the list length.

Space

O(1)

Only two pointers are used regardless of input size, so the auxiliary space is constant.

Pattern Spotlight

Fast & Slow Pointers (Cycle Detection in Linked List)

When detecting cycles in linked structures, use two pointers moving at different speeds; if a cycle exists, the faster pointer will eventually catch up to the slower one inside the cycle.

Solution

Python

1class Solution:
  def hasCycle(self, head: ListNode) -> bool:
      slow, fast = head, head
4
      while fast and fast.next:
          slow = slow.next
          fast = fast.next.next
          if slow == fast:
              return True
      
      return False

Step-by-Step Solution

Initialize Slow and Fast Pointers at Head

3	`slow, fast = head, head`

Objective

To set up two pointers starting at the head of the linked list for cycle detection.

Key Insight

Starting both pointers at the head ensures they traverse the same path initially. The difference in their speeds will reveal the presence of a cycle without extra space. This initialization is the foundation for the fast and slow pointer technique.

Interview Quick-Check

Core Logic

Both pointers start at the head to synchronize traversal and enable cycle detection through relative movement.

Common Pitfalls & Bugs

Failing to initialize both pointers at the head can cause incorrect detection or missed cycles.

Advance Pointers and Detect Cycle by Meeting

To move slow by one step and fast by two steps, checking for pointer equality to detect a cycle.

Return False if No Cycle Detected

To return false when the fast pointer reaches the end of the list, indicating no cycle.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 7 Critical

fast = fast.next.next

Move fast pointer two steps forward.

This line is the critical step that creates the speed difference between pointers, enabling the fast pointer to catch up to the slow pointer inside a cycle, which is the fundamental mechanism for cycle detection.

Line 8 Critical

if slow == fast:

Check if slow and fast pointers have met.

This equality check is the definitive condition for cycle detection; if slow equals fast, the linked list contains a cycle, and the algorithm can terminate early.

Full line-by-line criticality + rationale for all 7 lines available on Pro.

Test Your Understanding

Why does the fast pointer eventually meet the slow pointer if a cycle exists?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Linked List Cycle Detection from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Linked List Cycle Detection drill

or drill a free problem

1	`class Solution:`
2	`def hasCycle(self, head: ListNode) -> bool:`
3	`slow, fast = head, head`
4
5	`while fast and fast.next:`
6	`slow = slow.next`
7	`fast = fast.next.next`
8	`if slow == fast:`
9	`return True`
10
11	`return False`