52. Find Linked List Cycle Entry
If the list loops, identify the first node that a traversal from the head would encounter for a second time. Return that actual node object.
A new node with an equal value is not an answer. If following next links eventually reaches null, return null and preserve the original links.
Example 1
Input
N0→N1→N2→N3→N4→N5→N6, N6.next=N3
Output
N3
Explanation: μ=3,L=4. Detection meets at N4 after four rounds; recovery takes three one-step rounds to N3. The meeting is not the answer.
Example 2
Input
N0→N1→N2→N0
Output
N0
Explanation: μ=0. The positive-time meeting is already head and recovery performs zero moves.
Example 3
Input
N0(4)→N1(4)→null
Output
null
Explanation: Repeated values are not a cycle and must not be returned as an entry.
Constraints
0 <= nodes per input list <= 105-231 <= node.value <= 231 - 1- The next links may form one reachable cycle. Compare node identity, not repeated values.
Hints
Hint 1
First find a cycle meeting safely. It need not be the entry.
Hint 2
If slow took t steps and fast 2t, what must t satisfy modulo cycle length?
Hint 3
Move a fresh head pointer and the meeting pointer one step each; they first coincide at entry after μ steps.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Meeting differs from entry: tail three, cycle four
[0,0,0,0,0,0,0]
3
"N3"