Loading content...
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.
head = [3,2,0,-4], pos = 1Node at index 1 (value = 2)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.
head = [1,2], pos = 0Node at index 0 (value = 1)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.
head = [1], pos = -1null (no cycle)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