MediumLinked ListTwo PointersHash Table

Linked List Cycle II

1 approach, code in every language

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

A cycle occurs when the tail links back to an earlier node instead of terminating. That entry point is what you must locate. You should not modify the list, and ideally you solve it using only constant extra space.

Example 1

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

Output: Node at index 1 (value 2)

The tail loops back to the node with value 2, so the cycle begins there.

Example 2

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

Output: Node at index 0 (value 1)

The second node points back to the head, making the head the cycle entry.

Constraints

The number of nodes is in the range [0, 10^4].
-10^5 <= Node.val <= 10^5
pos is -1 (no cycle) or a valid 0-based index into the list.

Floyd's Algorithm, Two Phases

Detect the meeting point, then walk from head and from the meeting point in lockstep.

Loading animation…

Intuition

First we use the classic tortoise-and-hare collision to confirm a loop exists and to find some node inside it. The key insight is arithmetic: when the slow and fast pointers meet, the distance from the head to the cycle entry equals the distance from the meeting point to that same entry, measured around the loop. That is why resetting one pointer back to the head and then advancing both pointers one step at a time makes them collide exactly at the start of the cycle. If the fast pointer instead reaches null, there is no loop and we return null. The whole process stays in constant space.

Algorithm walkthrough

1Run slow (one step) and fast (two steps) from the head until they either meet or fast falls off the end.
2If fast or fast.next becomes null, there is no cycle, so return null.
3When slow equals fast, a cycle is confirmed; place a new pointer ptr at the head.
4Advance ptr and slow together one node at a time.
5The node where ptr and slow meet is the entrance of the cycle; return it.

Implementation

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                ptr = head
                while ptr is not slow:
                    ptr = ptr.next
                    slow = slow.next
                return ptr
        return None

Time

O(n)

Space

O(1)

Two linear phases, collision detection then entry alignment, with only a few pointers.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Linked List

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free