325. Find the Starting Point of a Cycle

Given the head of a singly linked list that may contain a cycle, return the value of the node where the cycle begins. If there is no cycle, return -1.

Use Floyd's algorithm: after detecting the meeting point, reset one pointer to head and advance both one step at a time — they meet at the cycle start.

Input: Array of node values and integer pos (0-indexed cycle entry, or -1 if no cycle).

Output: Value of the cycle-start node, or -1 if no cycle.

Examples

Input: [3,2,0,-4], pos=1
Output: 2
Explanation: Cycle starts at index 1 (value=2). Floyd: reset one pointer to head, both meet at node(2).

Input: [1,2], pos=0
Output: 1
Explanation: Cycle starts at index 0 (head, value=1).

Input: [1], pos=-1
Output: -1
Explanation: No cycle. Return -1.

Constraints

• 0<=nodes<=10^4
• -10^5<=Node.val<=10^5
• pos=-1 or 0<=pos<n

Asked by