Linked List Cycle II

Medium

Fast & Slow Pointers

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.

This extends the basic cycle detection to find the exact starting point of the cycle. After detecting a cycle with Floyd's algorithm, there's a beautiful mathematical property: if you reset one pointer to the head and move both pointers one step at a time, they will meet at the cycle's starting node.

Example 1

Input: head = [3,2,0,-4], pos = 1

Output: Node at index 1 (value = 2)

Explanation: There is a cycle in the linked list, where tail connects to the second node. The cycle begins at the node with value 2.

Example 2

Input: head = [1,2], pos = 0

Output: Node at index 0 (value = 1)

Explanation: There is a cycle in the linked list, where tail connects to the first node. The cycle begins at the node with value 1.

Example 3

Input: head = [1], pos = -1

Output: null

Explanation: There is no cycle in the linked list.

Constraints

•The number of nodes in the list is in the range [0, 10^4]
•-10^5 <= Node.val <= 10^5
•pos is -1 or a valid index in the linked-list

Show Hints (4)

Hint 1: First, can you detect if a cycle exists using the tortoise and hare technique?

Hint 2: Once the two pointers meet, there is a mathematical relationship between the meeting point and the cycle start.

Hint 3: Let the distance from head to cycle start be a, and from cycle start to meeting point be b. The cycle length is c. Can you express the distances traveled by each pointer?

Hint 4: After the meeting, if you put one pointer back at head and advance both pointers one step at a time, where will they meet?

Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor

Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?