Linked List Cycle (LC 141)

Pattern: Fast & Slow Pointers (Floyd’s cycle detection)
Difficulty: Easy
Key Concept: If a tortoise and hare move at 1 and 2 steps per tick, they meet inside the cycle if and only if a cycle exists.

Problem Statement

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

Return true if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is the index where tail connects (not passed as parameter); pos == -1 means no cycle.

Input: head of singly linked list.
Output: boolean.

---

1. Algorithm & Pseudocode

Brute force

1. Walk the list, store each node in a HashSet<ListNode>; if you see a node twice, cycle exists.
2. Or copy full structure—wasteful.

Pseudocode:

seen = empty set
while head != null:
    if head in seen: return true
    add head to seen
    head = head.next
return false

Optimal (Floyd)

1. slow = head, fast = head.
2. Loop: slow = slow.next, fast = fast.next.next.
3. If fast or fast.next is null → no cycle.
4. If slow == fast → cycle.

---

2. Step-by-Step Analysis (Beginner-Friendly)

Why HashSet works: Nodes are unique objects; revisiting same reference means a loop.

Why two pointers work: In a cycle, the hare laps the tortoise—they must coincide at some step inside the ring (mathematical invariant).

Why check fast and fast.next: Advancing fast two steps must guard null on both.

---

3. The Dry Run

List: 3 -> 2 -> 0 -> -4 with -4.next back to node 2 (the node with value 2).

step	slow position (val)	fast position (val)
0	3	3
1	2	0
2	0	2
3	-4	-4

---

4. Java Solution

Brute Force

import java.util.HashSet;
import java.util.Set;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> seen = new HashSet<>();
        while (head != null) {
            if (!seen.add(head)) {
                return true;
            }
            head = head.next;
        }
        return false;
    }
}

Time: O(n). Space: O(n).

Optimal

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

Time: O(n). Space: O(1).

---

5. The “Java vs. Others” Edge

• Set.add returns false if element existed—compact cycle check.
• Floyd avoids ListNode hashing concerns (default identity hash is fine in Java, but Floyd is standard).
• Follow-up find cycle start uses meeting point + reset one pointer to head (LC 142).

---

6. Complexity Summary

Approach	Time	Space	Notes
HashSet	O(n)	O(n)	Simple, extra memory
Floyd	O(n)	O(1)	Two pointers

---

ASCII — cycle

No cycle:

head
  |
  v
+---+    +---+    +---+
| 1 |--> | 2 |--> | 3 |--> null
+---+    +---+    +---+

With cycle (tail points back to middle):

                    +------------------+
                    |                  |
                    v                  |
+---+    +---+    +---+    +---+      |
| 1 |--> | 2 |--> | 3 |--> | 4 |------+
+---+    +---+    +---+    +---+

Fast / slow (conceptual):

slow -> 1 step per move
fast -> 2 steps per move
        (inside ring they eventually land on same node)