LeetCode · #141

Linked List Cycle Solution

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

Section One · Problem

Problem Statement

🏷️

Difficulty

Easy

🔗

LeetCode

Problem #141

🏗️

Pattern

Fast-Slow Pointers — Floyd's algorithm

Given head, return true if there is a cycle in the linked list — i.e., some node can be reached again by continuously following next. Otherwise return false.

Example

 Input: 3 → 2 → 0 → -4 → (back to 2)
Output: true // Tail connects to node at index 1 

Constraints

• 0 ≤ number of nodes ≤ 10⁴ • -10⁵ ≤ Node.val ≤ 10⁵

Section Two · Approach 1

HashSet — O(n) space

Traverse the list, storing each visited node in a HashSet. If you encounter a node already in the set, there's a cycle. If you reach null, no cycle.

Problem: O(n) extra space for the set. Floyd's cycle detection uses two pointers with O(1) space — no set needed.

Metric	Value
Time	O(n)
Space	O(n)

Section Three · Approach 2

Floyd's Tortoise & Hare — O(1) space

Use two pointers: slow moves 1 step at a time, fast moves 2 steps. If there's a cycle, fast will eventually lap slow and they'll meet. If fast reaches null, no cycle.

💡 Mental model: Two runners on a circular track. The fast runner laps the slow runner — guaranteed. On a straight track (no loop), the fast runner reaches the end first. If the slow and fast pointers ever point to the same node, you've confirmed a loop.

Algorithm

Step 1: slow = head, fast = head.
Step 2: While fast ≠ null and fast.next ≠ null:
slow = slow.next (1 step)
fast = fast.next.next (2 steps)
If slow == fast → return true.
Step 3: Return false.

🎯 Why they must meet:

Once fast enters the cycle, the gap between fast and slow decreases by 1 each step (fast gains 1 step per iteration).
Eventually the gap becomes 0 — they collide. This takes at most one full cycle length of iterations.

Section Four · Trace

Visual Walkthrough

Trace: 3 → 2 → 0 → -4 → (back to 2):

Floyd's Cycle Detection — slow vs fast pointer

Section Five · Implementation

Code — Java & Python

Java — Floyd's Algorithm

 class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
if (slow == fast) return true;
        }
return false;
    }
}

Python — Floyd's Algorithm

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

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
HashSet	O(n)	O(n)	Simple but uses extra memory
Floyd's ← optimal	O(n)	O(1)	Two pointers, no extra storage

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Empty list	`null`	fast is null → loop doesn't execute → false.
Single node, no cycle	`1 → null`	fast.next is null → false.
Single node, self-cycle	`1 → 1`	slow=1, fast=1's next is itself → both advance to 1 → true.
Cycle at tail	`1→2→3→(back to 3)`	Self-loop at last node. Fast enters cycle, laps slow.

⚠ Common Mistake: Checking fast.next without first checking fast != null. If fast reaches null (no cycle), accessing fast.next throws a NullPointerException. Always check both: fast != null && fast.next != null.

← Back to Linked List problems

LearningTree

LC 141 · Linked List Cycle — Solution & Explanation | DSA Guide