"""
p06 — Reverse Linked List
=========================
LeetCode 206 · Easy · Topics: Linked List, Recursion

Sections:
  1. ListNode helper (minimal, with __repr__)
  2. ITERATIVE — three-pointer dance (production-grade)
  3. RECURSIVE — for didactic comparison (O(N) stack)
  4. Helpers (list <-> Python list, length, equality)
  5. STRESS TEST — random + round-trip property
  6. EDGE CASES
"""

import random
import sys
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

    def __repr__(self) -> str:
        # Bounded preview to avoid infinite output on cycles
        out, node, k = [], self, 0
        while node and k < 12:
            out.append(str(node.val))
            node = node.next
            k += 1
        if node:
            out.append("...")
        return " -> ".join(out) if out else "None"


# ----------------------------------------------------------------------
# 2. ITERATIVE — O(N) time, O(1) space
# ----------------------------------------------------------------------
def reverse_iterative(head: Optional[ListNode]) -> Optional[ListNode]:
    # INVARIANT: at top of loop, `prev` is the head of the already-reversed prefix
    # and `curr` points to the next unprocessed node of the original list.
    # Line order MUST be: SAVE next -> REWIRE curr.next -> ADVANCE prev -> ADVANCE curr.
    prev: Optional[ListNode] = None
    curr = head
    while curr is not None:
        next_node = curr.next      # 1. SAVE before destroying
        curr.next = prev           # 2. REWIRE backward
        prev = curr                # 3. ADVANCE prev
        curr = next_node           # 4. ADVANCE curr
    return prev


# ----------------------------------------------------------------------
# 3. RECURSIVE — O(N) time, O(N) stack
# ----------------------------------------------------------------------
def reverse_recursive(head: Optional[ListNode]) -> Optional[ListNode]:
    # Base: empty or single node — already reversed.
    if head is None or head.next is None:
        return head
    new_head = reverse_recursive(head.next)
    # head.next is the old second node, now the tail of the reversed sublist.
    # Make it point back to head.
    head.next.next = head
    # CRITICAL: cut head's forward link, else we create a 2-cycle at the new tail.
    head.next = None
    return new_head


# ----------------------------------------------------------------------
# 4. Helpers
# ----------------------------------------------------------------------
def build(values: List[int]) -> Optional[ListNode]:
    dummy = ListNode()
    curr = dummy
    for v in values:
        curr.next = ListNode(v)
        curr = curr.next
    return dummy.next


def to_list(head: Optional[ListNode]) -> List[int]:
    out: List[int] = []
    seen: set[int] = set()
    while head is not None:
        if id(head) in seen:
            raise RuntimeError("cycle detected in output list")
        seen.add(id(head))
        out.append(head.val)
        head = head.next
    return out


# ----------------------------------------------------------------------
# 5. STRESS TEST — round-trip property + reference comparison
# ----------------------------------------------------------------------
def stress_test(iterations: int = 1000, max_n: int = 50) -> None:
    rng = random.Random(42)
    sys.setrecursionlimit(10_000)
    for it in range(iterations):
        n = rng.randint(0, max_n)
        values = [rng.randint(-1000, 1000) for _ in range(n)]
        expected = list(reversed(values))

        # iterative
        it_result = to_list(reverse_iterative(build(values)))
        assert it_result == expected, f"iterative wrong on {values}: got {it_result}"

        # recursive
        rc_result = to_list(reverse_recursive(build(values)))
        assert rc_result == expected, f"recursive wrong on {values}: got {rc_result}"

        # round-trip property: reverse(reverse(x)) == x
        round_trip = to_list(reverse_iterative(reverse_iterative(build(values))))
        assert round_trip == values, f"round-trip failed on {values}: got {round_trip}"

    print(f"stress_test PASSED — {iterations} iterations")


# ----------------------------------------------------------------------
# 6. EDGE CASES
# ----------------------------------------------------------------------
def edge_cases() -> None:
    cases = [
        ([], "empty list"),
        ([1], "single node — the off-by-one trap"),
        ([1, 2], "two-node — smallest non-trivial"),
        ([1, 2, 3, 4, 5], "canonical"),
        ([7, 7, 7, 7], "all-same-value (output indistinguishable from input)"),
        ([-1, 0, 1], "negative + zero"),
        (list(range(100)), "length 100"),
    ]
    for values, label in cases:
        expected = list(reversed(values))
        it_out = to_list(reverse_iterative(build(values)))
        rc_out = to_list(reverse_recursive(build(values)))
        ok = it_out == expected and rc_out == expected
        status = "PASS" if ok else "FAIL"
        sample = expected if len(expected) <= 8 else f"{expected[:4]}...{expected[-4:]}"
        print(f"  [{status}] {label}: expected={sample}")


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