Linked List Cycle II

Mediumlinked-listtwo-pointers
Category: Linked List
Companies that ask this question:
AmazonMicrosoftFacebookGoogle
LeetCode →NeetCode →

Approach

Linked List Cycle II

Problem Statement

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

A cycle exists if there is a node in the list that can be reached again by continuously following the next pointer.

Do not modify the linked list.

Approach: Floyd's Cycle Detection Algorithm (Two-Phase)

This problem extends Floyd's algorithm to not just detect a cycle, but find where it begins.

Algorithm

Phase 1: Detect if cycle exists

  1. Use slow (1 step) and fast (2 steps) pointers
  2. If they meet, there's a cycle
  3. If fast reaches null, there's no cycle

Phase 2: Find cycle entrance

  1. Reset one pointer to head
  2. Move both pointers one step at a time
  3. Where they meet is the cycle entrance

Why This Works - The Math

Let's say:

  • L = distance from head to cycle entrance
  • C = cycle length
  • When slow and fast meet, slow traveled L + a distance (where a is distance into cycle)

Since fast travels twice as fast:

  • Fast traveled L + a + nC (for some number of cycles n)
  • Since fast = 2 × slow: L + a + nC = 2(L + a)
  • Simplifying: L = nC - a

This means the distance from head to entrance equals the distance from meeting point to entrance!

Visual Example

For list: 3 → 2 → 0 → -4 → (back to 2)

Phase 1: Detect cycle
  Head
   ↓
   3 → 2 → 0 → -4
       ↑_________|

Slow and fast meet at node -4

Phase 2: Find entrance
  ptr1         ptr2
   ↓            ↓
   3 → 2 → 0 → -4
       ↑_________|

Move both 1 step at a time...
They meet at node 2 (the entrance!)

Time Complexity

  • Time: O(n) where n is the number of nodes
    • Phase 1: O(n) to detect cycle
    • Phase 2: O(n) to find entrance
  • Space: O(1) - only two pointers

Alternative Approaches

1. Hash Set

  • Store visited nodes in a hash set
  • First node we see twice is the entrance
  • Time: O(n), Space: O(n)
  • Simple but uses extra space

2. Modify Node Values

  • Mark visited nodes by changing their value
  • First marked node is the entrance
  • Time: O(n), Space: O(1)
  • Not allowed as it modifies the input

Key Insights

  1. Floyd's algorithm is elegant and uses constant space
  2. The mathematical relationship between distances is crucial
  3. Two distinct phases: detection and finding entrance
  4. No need to calculate cycle length explicitly
  5. Works for any cycle position and length

Solution

java
1/**
2 * Linked List Cycle II - Floyd's Cycle Detection Algorithm (Two-Phase)
3 *
4 * Time Complexity: O(n)
5 * Space Complexity: O(1)
6 */
7
8class ListNode {
9    int val;
10    ListNode next;
11    ListNode(int x) {
12        val = x;
13        next = null;
14    }
15}
16
17public class Solution {
18    public ListNode detectCycle(ListNode head) {
19        // Edge case: empty list or single node without cycle
20        if (head == null || head.next == null) {
21            return null;
22        }
23
24        // Phase 1: Detect if cycle exists using Floyd's algorithm
25        ListNode slow = head;
26        ListNode fast = head;
27
28        while (fast != null && fast.next != null) {
29            slow = slow.next;
30            fast = fast.next.next;
31
32            // If they meet, cycle exists
33            if (slow == fast) {
34                // Phase 2: Find cycle entrance
35                // Reset one pointer to head
36                slow = head;
37
38                // Move both pointers one step at a time
39                // They will meet at the cycle entrance
40                while (slow != fast) {
41                    slow = slow.next;
42                    fast = fast.next;
43                }
44
45                // Return the entrance node
46                return slow;
47            }
48        }
49
50        // Fast reached end, no cycle
51        return null;
52    }
53}
54
55// Alternative: Hash Set Approach
56class Solution2 {
57    public ListNode detectCycle(ListNode head) {
58        Set<ListNode> visited = new HashSet<>();
59        ListNode current = head;
60
61        while (current != null) {
62            // If we've seen this node before, it's the entrance
63            if (visited.contains(current)) {
64                return current;
65            }
66
67            // Mark node as visited
68            visited.add(current);
69            current = current.next;
70        }
71
72        // No cycle found
73        return null;
74    }
75}
76
Loading visualizer...