Linked List Cycle II — DSA

Problem

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

3 → 2 → 0 → -4
    ↑        |
    └────────┘         →   returns the node with value 2 (where the tail links back)

The cycle's entry point is the first node that's reached twice when following next pointers.
Don't modify the list.
Follow-up: can you solve it in O(1) extra space? This builds on the fast/slow pointer technique from Linked List Cycle, plus a neat distance argument that pinpoints the cycle's start.

Examples

Example 1

Input: head = [3,2,0,-4], pos = 1 (tail connects to index 1)

Output: node with value 2

Explanation: The cycle begins at the node with value 2.

Example 2

Input: head = [1], pos = -1

Output: null

Explanation: No cycle.

Constraints

•The number of nodes is in the range [0, 10^4]
•-10^5 <= Node.val <= 10^5

Hints

Hint 1

First detect whether a cycle exists at all using Floyd's slow/fast pointer technique — the same approach as the basic cycle-detection problem.

Hint 2

The interesting part is what happens after slow and fast meet inside the cycle: that meeting point isn't the cycle's start, but it has an exact mathematical relationship to it.

Hint 3

Try resetting one pointer to head and moving both remaining pointers one step at a time — where do they meet?

Solutions

public ListNode detectCycleBruteForce(ListNode head) {
    Set<ListNode> visited = new HashSet<>();
    ListNode curr = head;
    while (curr != null) {
        if (!visited.add(curr)) return curr; // first node we've already seen IS the cycle's start
        curr = curr.next;
    }
    return null;
}

Time: O(n) · Space: O(n)