Locate a Cycle Entry without Changing the List
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Return the original node at which a singly linked-list cycle begins, or null if there is no cycle. Do not modify the list. A test display may specify the tail's zero-based connection index `pos`, with -1 for no cycle, but the function receives only `head`.
```cpp
ListNode* detectCycle(ListNode* head);
```
Keep the pointer return. Returning the entry's value or a newly created node is insufficient.
### Examples
```text
First-visit values: [7,2,9,2,5]; tail links to index 2
Output reference: the original node at index 2, value 9
```
```text
Values: [4,6]; tail links to null (pos=-1)
Output: null
```
### Constraints
- The list has between 0 and 10000 distinct reachable nodes.
- Node values lie between -100000 and 100000.
- `pos` is -1 or a valid index in the displayed list.
### Optional follow-up
Use only `O(1)` extra memory.
Overview: Locate the original entry node of a linked-list cycle without modifying links and with constant extra space.
