Given the head of a linked list, determine whether a cycle exists and return the node where the cycle begins if one is present.
Problem
You are given the head of a singly linked list. The list may contain a cycle: following the next pointers may eventually lead back to an earlier node.
Return the node where the cycle begins. If the list does not contain a cycle, return null.
The answer must identify the actual node object, not just its value.
Input Format
- A singly linked list head node is provided.
- Each node contains an integer value and a
nextpointer.
Output Format
- Return the first node that lies on the cycle, or
nullif no cycle exists.
Constraints
- The linked list may be empty.
- Node values are not guaranteed to be unique.
- You should solve this in linear time with constant extra space.
Hints
- First determine whether a cycle exists.
- If two pointers move at different speeds, think about what it means when they meet.
- After a meeting point is found, there is a standard way to locate the cycle entry.
Input Format
head: head of a singly linked list- Each node has fields
valandnext
Output Format
- Return the node where the cycle starts, or
nullif the list is acyclic
Constraints
- Linear time
- Constant extra space
- The list may be empty
- Node values may repeat
Example 1
Input
head = [3,2,0,-4], pos = 1
Output
node with value 2
Explanation
The tail connects back to the second node, so the cycle starts at the node whose value is 2.
Example 2
Input
head = [1,2], pos = 0
Output
node with value 1
Explanation
The last node points back to the head, so the cycle begins at the first node.
Show 1 more example
Example 3
Input
head = [1], pos = -1
Output
null
Explanation
The list does not contain a cycle.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.