Given the head node of a linked list, return the node where a cycle begins. If no cycle exists, return null. The linked list cannot be modified.

A cycle is present if a node can be reached again by continuously following the next pointer. The evaluation system internally uses an integer pos to denote the zero-based index where the tail connects to a node in the list, but pos is not passed as a argument.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: Node at index 1
Explanation: The tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: Node at index 0
Explanation: The tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: null
Explanation: No cycle exists.

Constraints:

• Node count: 0 to 10^4
• Node values: -10^5 to 10^5
• pos is -1 or a valid index

Advanced: Solve with O(1) memory.

Using two pointers moving at different speeds, this problem can be solved efficiently. Consider a slow pointer advancing one node per step and a fast pointer moving two nodes per step.

Let:

• a = distance from head to cycle start
• b = cycle length
• k = distance from cycle start to meeting point

When the pointers meet, the slow pointer has traveled a + k nodes. The fast pointer has traveled a + k + n * b nodes, where n is a positive integer representing extra cycles. Since fast moves twice as fast: 2(a + k) = a + k + n * b Simplifying: a + k = n * b Thus, a = n * b - k.

This implies that the distance from head to cycle start (a) equals the distance from the meeting point moving forward within the cycle to reach the start again (n * b - k).

After detecting a meeting point, reset one pointer to head. Move both pointers one node per step. They will meet at the cycle start because the pointer from head travels a steps, and the pointer from the meeting point travels n * b - k steps, wich is exactly a.

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class CycleDetector {
public:
    ListNode* findCycleStart(ListNode* startNode) {
        ListNode* tortoise = startNode;
        ListNode* hare = startNode;
        
        while (hare != nullptr && hare->next != nullptr) {
            tortoise = tortoise->next;
            hare = hare->next->next;
            
            if (tortoise == hare) {
                hare = startNode;
                while (hare != tortoise) {
                    hare = hare->next;
                    tortoise = tortoise->next;
                }
                return hare;
            }
        }
        return nullptr;
    }
};