Linked List Cycle II – Solution & Complexity

Watch: Linked List Cycle II with fast and slow pointers

Run slow and fast pointers until they meet, but don't return the meeting point. Move one pointer back to the head and step both by one: the head is as far from the cycle start as the meeting point is, plus whole laps, so they meet at the start. O(n) time, O(1) space.

Solution Walkthrough

  1. Step 1: Recognize the Pattern

    The key pattern is: Floyd's tortoise-and-hare — advance slow by one step and fast by two; if they meet inside a cycle, resetting one pointer to the head and advancing both by one step at a time makes them meet exactly at the cycle's start.

  2. Step 2: Build the Algorithm

    Advance one state transition at a time. Mark or update state before exploring dependent work.

  3. Step 3: Check Edge Cases

    Test empty or minimal input, skewed shapes, duplicates where allowed, and impossible outcomes.

  4. Step 4: Solution and Complexity

    Time: O(n) — each pointer visits at most O(n) nodes before either reaching the end or meeting inside the cycle. Space: O(1) — only a constant number of index variables are used, no visited-set.

    This problem reuses the same plain-array nextIndices encoding as linked-list-cycle (rather than a real ListNode structure), since a genuinely cyclic linked-list value isn't something the judge's structural list/tree conversion supports as an input or output — the array of next-indices sidesteps that entirely while still exercising real cycle-detection logic in all 5 languages.

    def detect_cycle(nextIndices: list[int]) -> int:
        if not nextIndices:
            return -1
    
        slow = fast = 0
        while fast != -1 and nextIndices[fast] != -1:
            slow = nextIndices[slow]
            fast = nextIndices[fast]
            if fast == -1:
                break
            fast = nextIndices[fast]
            if slow == fast:
                ptr1, ptr2 = 0, slow
                while ptr1 != ptr2:
                    ptr1 = nextIndices[ptr1]
                    ptr2 = nextIndices[ptr2]
                return ptr1
    
        return -1

FAQ