šŸ”— LeetCode

Linked List Cycle

Easytwo pointersAmazonMicrosoft

Given head, the head of a linked list, determine if the linked list has a cycle in it.

Examples

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

Constraints

    šŸ’” Hints

    Hint 1

    Can you use two pointers, one moving faster than the other?

    Algorithm Complexity

    Official asymptotic Big-O runtime and auxiliary memory analysis

    Linear
    Algorithmic Approach

    Floyd cycle finding algorithm.

    Time ComplexityO(N)
    Why:

    Floyd's Tortoise and Hare algorithm guarantees the fast pointer meets slow in at most N steps if a cycle exists, or reaches null in N/2 steps.

    Space ComplexityO(1)
    Why:

    Only two pointer variables (slow and fast) are maintained in memory without extra node sets.

    Big-O Growth CurveLinear (O(N))
    Execution time scales directly in proportion to the input size.

    šŸ” Dry Run

    Solutionā± O(N) | šŸ’¾ O(1)
    slowā†“
    fastā†“
    head
    3
    2
    0
    -4