DSA problem

Linked List Cycle II

MediumFast and Slow PointersPattern: Fast and Slow Pointerstop75FreeAmazonMicrosoftGoogleMetaAppleBloomberg

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. You are not allowed to modify the linked list, and your algorithm should use only constant extra space.

A direct way to solve this is to walk the list and store every visited node in a hash set; the first node that you re-encounter is the entry point of the cycle. This is correct and easy to write, but it uses O(n) extra space — disallowed by the problem.

The optimal approach is Floyd's tortoise-and-hare in two phases, which finds the cycle entry in O(n) time and O(1) space. Phase 1 detects whether a cycle exists at all: advance slow by one node and fast by two nodes per iteration; if they ever meet inside the list, a cycle exists, and they meet at some node we will call the meeting point. If fast runs off the end first, there is no cycle and we return null.

Phase 2 locates the entry node using a clean piece of arithmetic. Let L be the distance from the head to the cycle entry, C the cycle length, and K the distance from the entry to the meeting point. Since fast moved twice as far as slow when they met, we have 2 * (L + K) = L + K + n * C for some integer n, which simplifies to L = n * C - K. In words: starting one new pointer at head and another at the meeting point, and advancing both one step at a time, they must collide exactly at the cycle entry. So we reset a pointer to head, walk both pointers one step at a time, and return the node where they meet.

Examples

Example 1

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

Output: tail connects to node index 1

Explanation: The tail node (value -4) links back to the node at index 1 (value 2), so the cycle begins at the node with value 2. The algorithm returns a reference to that node.

Example 2

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

Output: tail connects to node index 0

Explanation: The tail node (value 2) links back to the head (value 1), so the entire list is the cycle and its entry is the head itself.

Example 3

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

Output: no cycle

Explanation: A single node with no self-loop has no cycle, so the function returns null.

Constraints

The number of the 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 (used only to construct the test, not passed in).
You must solve it using O(1) extra memory.

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

linked-listtwo-pointersfast-slow-pointerscycle-detection

Browse all DSA problems