"""
p08 — Linked List Cycle
=======================
LeetCode 141 · Easy · Topics: Linked List, Two Pointers, Hash Table

Sections:
  1. ListNode
  2. HashSet brute force — O(N) space (correctness oracle)
  3. Floyd's tortoise-and-hare — O(1) space (production)
  4. build_with_cycle helper
  5. Stress test (random with and without cycles)
  6. Edge cases
"""

import random
from typing import List, Optional


# ----------------------------------------------------------------------
# 1. ListNode
# ----------------------------------------------------------------------
class ListNode:
    __slots__ = ("val", "next")

    def __init__(self, val: int = 0, next_node: "Optional[ListNode]" = None):
        self.val = val
        self.next = next_node


# ----------------------------------------------------------------------
# 2. HashSet brute force — O(N) time, O(N) space
# ----------------------------------------------------------------------
def has_cycle_hashset(head: Optional[ListNode]) -> bool:
    # Use id(node) — IDENTITY, not value. Two distinct nodes can hold equal vals.
    seen: set[int] = set()
    node = head
    while node is not None:
        if id(node) in seen:
            return True
        seen.add(id(node))
        node = node.next
    return False


# ----------------------------------------------------------------------
# 3. Floyd's tortoise and hare — O(N) time, O(1) space
# ----------------------------------------------------------------------
def has_cycle(head: Optional[ListNode]) -> bool:
    # INVARIANT inside the cycle: gap = (fast_pos - slow_pos) mod C increases
    # by exactly 1 each iteration (fast gains 2, slow gains 1). Since gap is
    # bounded in [0, C-1], it MUST hit 0 within C iterations — that's the meet.
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next            # advance 1
        fast = fast.next.next       # advance 2 (guarded above)
        if slow is fast:
            return True
    return False


# ----------------------------------------------------------------------
# 4. Helper — build list with optional cycle injection
# ----------------------------------------------------------------------
def build_with_cycle(values: List[int], cycle_at: int = -1) -> Optional[ListNode]:
    """
    cycle_at = -1: no cycle.
    cycle_at = k:  tail.next points back to the k-th node (0-indexed).
    """
    if not values:
        return None
    nodes = [ListNode(v) for v in values]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    if cycle_at >= 0:
        if cycle_at >= len(nodes):
            raise ValueError("cycle_at out of range")
        nodes[-1].next = nodes[cycle_at]
    return nodes[0]


# ----------------------------------------------------------------------
# 5. Stress test
# ----------------------------------------------------------------------
def stress_test(iterations: int = 1000, max_n: int = 50) -> None:
    rng = random.Random(42)
    for it in range(iterations):
        n = rng.randint(1, max_n)
        values = [rng.randint(-1000, 1000) for _ in range(n)]
        if rng.random() < 0.5:
            cycle_at = rng.randint(0, n - 1)
            expected = True
        else:
            cycle_at = -1
            expected = False
        h1 = build_with_cycle(values, cycle_at)
        h2 = build_with_cycle(values, cycle_at)
        a = has_cycle_hashset(h1)
        b = has_cycle(h2)
        assert a == expected, f"hashset wrong: vals={values} cycle_at={cycle_at} got={a}"
        assert b == expected, f"floyd wrong: vals={values} cycle_at={cycle_at} got={b}"
    print(f"stress_test PASSED — {iterations} iterations")


# ----------------------------------------------------------------------
# 6. Edge cases
# ----------------------------------------------------------------------
def edge_cases() -> None:
    cases = [
        (None, False, "empty"),
        (build_with_cycle([1], -1), False, "single, no cycle"),
        (build_with_cycle([1], 0), True, "single self-loop — the off-by-one trap"),
        (build_with_cycle([1, 2], 0), True, "two-node cycle to head"),
        (build_with_cycle([1, 2, 3, 4], 0), True, "entire list is the cycle"),
        (build_with_cycle([3, 2, 0, -4], 1), True, "canonical cycle to mid"),
        (build_with_cycle([1, 1, 1, 1], -1), False, "all-equal values, no cycle (HashSet-on-val trap)"),
        (build_with_cycle(list(range(50)), 49), True, "cycle at tail (self-loop at end)"),
    ]
    for head, expected, label in cases:
        got_set = has_cycle_hashset(head)
        # rebuild for Floyd's — has_cycle_hashset reads nodes but doesn't mutate
        # so the same head is fine; the comment is for clarity
        got_fl = has_cycle(head)
        ok = got_set == expected and got_fl == expected
        status = "PASS" if ok else "FAIL"
        print(f"  [{status}] {label}: expected={expected} hashset={got_set} floyd={got_fl}")


if __name__ == "__main__":
    print("=== Edge cases ===")
    edge_cases()
    print("\n=== Stress test ===")
    stress_test()