Start of LinkedList Cycle

Medium·Tagslinked-listtwo-pointershash-table

Problem Statement

Given the head of a Singly LinkedList that contains a cycle, write a function to find the starting node of the cycle. If there is no cycle, return `null`.

Examples

Example 1

Input

head: [1, 2, 3, 4, 5, 6], pos: 2

Linked list

Output

"3"

Why

The linked list has a cycle where the tail (6) connects back to the node at index 2, which has the value 3.

Example 2

Input

head: [1, 2, 3, 4, 5], pos: 0

Linked list

Output

"1"

Why

The linked list has a cycle where the tail (5) connects back to the head node (1).

Example 3

Input

head: [1, 2, 3], pos: -1

Linked list

Output

"null"

Why

The linked list does not have a cycle.

Constraints

•0 <= Number of Nodes <= 10000
•-100000 <= Node.val <= 100000
•pos is -1 or a valid index in the linked-list.

Hints

Stuck? Reveal a nudge toward the right pattern, one step at a time.

Hint 1

You can use a Hash Set to store nodes you have already visited. The first node you see twice is the start of the cycle. However, this takes O(N) space. Can you do it in O(1) space?

Hint 2

Use the Fast and Slow pointers to find if a cycle exists. If they meet, you know there is a cycle.

Hint 3

Once they meet, take a step back and think about the math. The distance from the head of the list to the start of the cycle is equal to the distance from the meeting point to the start of the cycle!

Hint 4

Reset one of the pointers back to the head of the list. Then, move BOTH pointers one step at a time. The exact node where they collide again is the start of the cycle.