Linked List Cycle

Detect if a linked list has a cycle.

10 min read

Time: O(n)

Space: O(1)

Solve on LeetCode

Problem Understanding

Given the head of a linked list, determine if the linked list has a cycle in it. A cycle occurs if a node in the list can be reached again by continuously following the next pointer.

Attempt 1: Hash Set (Brute Force)

We can iterate through the list and store each node we visit in a Hash Set. Before visiting a node, we check if it's already in the set. If it is, we found a cycle. If we reach null, there is no cycle.

Drawback: This uses O(N) extra space to store references to all nodes.

Visualizing the Issue

Using O(N) space is acceptable, but can we do better? Can we detect a cycle using only O(1) space without modifying the list structure?

The Intuition: Floyd's Cycle Finding

Imagine two runners on a circular track. One is fast (Hare) and one is slow (Tortoise). If there is a loop, the Fast runner will eventually lap the Slow runner and they will meet explicitly inside the loop. If there is no loop, the Fast runner will just finish the race (reach null) first.

Interactive Walkthrough

Step 1 / 1

Empty List

Initializing...

Custom Input

Watch the 'Tortoise and Hare' race. See how the Fast pointer catches the Slow pointer.

Dry Run Table

Input: 3 -> 2 -> 0 -> -4 (cycle to index 1, value 2)

Step	Slow (Val)	Fast (Val)	Action
Start	3	3	Init
1	2	0	Slow moves 1, Fast moves 2
2	0	2	Slow moves 1, Fast moves 2
3	-4	-4	Meet! Cycle Detected

The Solution Template

Floyd's Cycle Finding Algorithm.

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

Edge Cases & Common Mistakes

Empty List: head is null (return false).
Single Node: No cycle possible unless it points to itself.
No Cycle: fast reaches null safely.

Time & Space Analysis

Time: O(N). In worst case (no cycle), we visit N nodes. If there is a cycle, the fast pointer catches slow quickly.
Space: O(1). Only two pointers used.

Summary

Using two pointers moving at different speeds allows us to detect cycles efficiently without using extra memory.

Previous Problem

Min Arrows to Burst Balloons

Next Problem

Remove Nth Node From End