#8MediumLinked Lists· Fast and Slow Pointers

Linked List Cycle Entry

You are given the `head` of a singly linked list that may contain a cycle: following `next` pointers from some node eventually returns to that node. Return the 0-based position of the node where the cycle begins, counting from `head`. If the list has no cycle, return `-1`. For testing, the list is described by its values `head` and an integer `pos`: the tail's `next` pointer is connected to the node at index `pos`, or to null when `pos = -1`. Your function only receives the head node; `pos` is not passed to it. Do not modify the list.

Input format

head: array of integers (node values from head to tail), pos: index the tail links back to, or -1 for no cycle

Output format

Integer: 0-based index of the first node in the cycle, or -1

Examples

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

Output: 1

The tail (-4) links back to the node at index 1 (value 2), where the cycle starts.

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

Output: -1

The single node points to null, so there is no cycle.

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

Output: 2

All values are equal, so the entry must be identified by node identity: it is the node at index 2.

Constraints

0 <= number of nodes <= 10^4
-10^5 <= Node.val <= 10^5
pos is -1 or a valid index into the list
Values may repeat, so identify nodes by identity, not by value.

Study first

Linked Lists & Pointer Nodes

#linked-lists
#two-pointers
#fast-slow-pointers
#cycle-detection