Linked List Cycle II

Description

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

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

Constraints:

• The number of the nodes in the list is in the range [0, 104].
• -105 <= Node.val <= 105
• pos is -1 or a valid index in the linked-list.

Follow up: Can you solve it using O(1) (i.e. constant) memory?

1. Brute Force Solution (Hash Set)

• Intuition: Walk through the linked list and keep track of every node you visit in a hash set. The very first node you encounter that is already in your set is the starting point of the cycle.
• Algorithm:

1. Initialize an empty hash set of nodes.
2. Traverse the list using a curr pointer.
3. If curr exists in the set, return curr.
4. Otherwise, add curr to the set and move to curr.next.
5. If curr reaches null, return null.

public class Solution {
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> visited = new HashSet<>();
        ListNode curr = head;
 
        while (curr != null) {
            if (visited.contains(curr)) {
                return curr; // First repeated node is the cycle start
            }
            visited.add(curr);
            curr = curr.next;
        }
 
        return null; // No cycle
    }
}
 

• Complexity:
• Time: $O(N)$
• Space: $O(N)$

---

2. Most Optimized Solution (Floyd’s Cycle Detection)

• Intuition:

1. Find Intersection: Move a slow pointer by 1 step and a fast pointer by 2 steps. If there is a cycle, they will eventually collide.
2. Find Cycle Start: Reset one pointer (entry) to head, keep the other pointer (slow) at the meeting point, and move both 1 step at a time. The node where they meet is the start of the cycle.

• Why it Works (Visualizing the Math):
• Let distance from head to cycle start = $A$.
• Distance from cycle start to meeting point = $B$.
• Distance from meeting point back to cycle start = $C$.
• Slow moved distance: $A+B$.
• Fast moved distance: $A+B+C+B=A+2B+C$.
• Since Fast travels twice as fast: $2(A+B)=A+2B+C⟹2A+2B=A+2B+C⟹A=C$.
• Because $A=C$, the distance from head to the start of the loop is identical to the distance from the collision point to the start of the loop!

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
 
        // Phase 1: Detect cycle
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
 
            // Cycle detected
            if (slow == fast) {
                // Phase 2: Find cycle start node
                ListNode entry = head;
                while (entry != slow) {
                    entry = entry.next;
                    slow = slow.next;
                }
                return entry;
            }
        }
 
        return null; // No cycle
    }
}
 

• Complexity:
• Time: $O(N)$
• Space: $O(1)$