JuniorJunior (1–3 yrs)CodingPythonAmazonMicrosoftAdobe

Detect cycle Floyd

Explain Floyd’s cycle detection for a linked list. How do you find the cycle start?

Answers use simple, clear English.

Time: O(n)Space: O(1)

Quick interview answer

Slow+fast pointers: if they meet, cycle exists. To find entrance: reset one pointer to head; both move 1 step — meeting point is start (math of equal distance). O(1) space vs hash set of nodes.

Detailed answer

Slow+fast pointers: if they meet, cycle exists. To find entrance: reset one pointer to head; both move 1 step — meeting point is start (math of equal distance). O(1) space vs hash set of nodes.

Real example & use case

Corrupt next pointers in memory allocator freelist.

Pros & cons

Pros: O(1) space. Cons: harder proof under time pressure.

Code example

def detect_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            slow = head
            while slow is not fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None

Practice code · python (view only · no execution)

def detect_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            slow = head
            while slow is not fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None

#dsa#linked-list#floyd