Circular List Entry Point

Medium

Given the starting node (head) of a singly linked list, determine whether the list contains a cycle (a loop where traversing the list eventually leads back to a previously visited node). If a cycle exists, return the node where the cycle begins — that is, the first node that is part of the cycle when traversing from the head. If no cycle exists in the list, return null . A cycle exists in a linked list when following the next pointers continuously from the head eventually leads to a node that has already been visited. The cycle entry point is the specific node where the tail of the list connects back, forming the loop. Important: The linked list must not be modified during or after your algorithm executes. Your solution should only inspect the structure to detect and locate any cycles. Implementation Note: Internally, a position value pos indicates which node (0-indexed from head) the tail's next pointer connects to. A value of -1 means the tail points to null (no cycle). This pos value is not provided to your function — it is only used to construct the test cases. Your function receives only the head node and must determine the cycle entry point (or absence of cycle) independently.

Example 1

Input

head = [3,2,0,-4], pos = 1

Output

Node at index 1 (value = 2)

Explanation

The linked list contains nodes with values 3 → 2 → 0 → -4. The last node (-4) has its next pointer connected back to the node at index 1 (value = 2), creating a cycle. The function should return a reference to the node with value 2, which is the entry point of the cycle.

Example 2

Input

head = [1,2], pos = 0

Output

Node at index 0 (value = 1)

Explanation

The list has two nodes: 1 → 2. The tail node (2) connects back to the head node (1), forming a cycle. The cycle entry point is the head itself, so we return the node with value 1.

Example 3

Input

head = [1], pos = -1

Output

null (no cycle)

Explanation

The list contains a single node with value 1, and its next pointer is null. Since there is no cycle in the list, the function returns null.

Constraints

The number of nodes in the list is in the range [0, 10⁴].
-10⁵ ≤ Node.val ≤ 10⁵
pos is -1 or a valid index (0-indexed) in the linked list.
If pos is -1, the list has no cycle (tail.next = null).
If pos is a valid index, the tail node's next pointer connects to the node at that index.