Linked List Cycle II, thesarfo

You’re given the head of a singly linked list. If there is a cycle in the list, return the node where the cycle begins. If there is no cycle, return null. The goal is to identify the start of the loop, not just whether one exists. (LeetCode 142)

Approach 1 — HashMap (brute force, O(n) space): traverse the list, storing each visited node in a map. If a node reappears during traversal, it must be the start of the cycle.

public class Solution {
    public ListNode detectCycle(ListNode head) {
        Map<ListNode, Boolean> visited = new HashMap<>();
        ListNode current = head;

        while (current != null) {
            if (visited.containsKey(current)) {
                return current;
            }
            visited.put(current, true);
            current = current.next;
        }

        return null;
    }
}

Approach 2 — Floyd’s Tortoise and Hare (O(1) space): use two pointers moving at different speeds. If a cycle is detected, reset one pointer to the head and move both pointers one step at a time — the node where they meet again is the start of the cycle.

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                ListNode entry = head;
                while (entry != slow) {
                    entry = entry.next;
                    slow = slow.next;
                }
                return entry;
            }
        }

        return null;
    }
}

Why this works: when slow and fast meet inside the loop, the distance from head to the start of the loop equals the distance from the meeting point to the start of the loop if you continue moving in the loop.