Linked List Cycle II Python Solution

lcpy gen -n 142   # by problem number
lcpy gen -s linked_list_cycle_ii   # by problem name

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

from leetcode_py import ListNode


class Solution:
    # Time: O(n)
    # Space: O(1)
    def detect_cycle(self, head: ListNode[int] | None) -> ListNode[int] | None:
        if not head:
            return None

        slow: ListNode[int] | None = head
        fast: ListNode[int] | None = head

        # Phase 1: Detect if cycle exists using Floyd's algorithm
        has_cycle = False
        while fast and fast.next:
            assert slow is not None
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                has_cycle = True
                break

        if not has_cycle:
            return None

        # Phase 2: Find the start of the cycle
        slow = head
        assert fast is not None  # fast is guaranteed to be a valid node here
        while slow is not fast:
            assert slow is not None
            slow = slow.next
            assert fast.next is not None
            fast = fast.next

        return slow