"""
p07 — Merge Two Sorted Lists
============================
LeetCode 21 · Easy · Topics: Linked List, Recursion

Sections:
  1. ListNode
  2. ITERATIVE — dummy node + splice + leftover attach (production)
  3. RECURSIVE — for didactic comparison
  4. Helpers (build, to_list, is_sorted)
  5. STRESS TEST — random sorted pairs vs sorted-Python-list oracle
  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:
        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(N1 + N2) time, O(1) space
# ----------------------------------------------------------------------
def merge_two_lists(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    # INVARIANT: at top of loop, `dummy.next ... tail` is a sorted list of all
    # nodes consumed so far; remaining l1 and l2 are sorted suffixes whose
    # first elements are >= tail.val (when tail != dummy).
    dummy = ListNode()
    tail = dummy
    while l1 is not None and l2 is not None:
        # `<=` ensures stability w.r.t. l1 (ties from l1 go first)
        if l1.val <= l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next
    # Leftover tail attach in O(1) — the remainder is already sorted.
    tail.next = l1 if l1 is not None else l2
    return dummy.next


# ----------------------------------------------------------------------
# 3. RECURSIVE — O(N1+N2) time, O(N1+N2) stack
# ----------------------------------------------------------------------
def merge_two_lists_recursive(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    if l1 is None:
        return l2
    if l2 is None:
        return l1
    if l1.val <= l2.val:
        l1.next = merge_two_lists_recursive(l1.next, l2)
        return l1
    l2.next = merge_two_lists_recursive(l1, l2.next)
    return l2


# ----------------------------------------------------------------------
# 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 in output")
        seen.add(id(head))
        out.append(head.val)
        head = head.next
    return out


def is_sorted(vals: List[int]) -> bool:
    return all(vals[i] <= vals[i + 1] for i in range(len(vals) - 1))


# ----------------------------------------------------------------------
# 5. STRESS TEST
# ----------------------------------------------------------------------
def stress_test(iterations: int = 1000, max_n: int = 30) -> None:
    rng = random.Random(42)
    sys.setrecursionlimit(10_000)
    for it in range(iterations):
        n1 = rng.randint(0, max_n)
        n2 = rng.randint(0, max_n)
        a = sorted(rng.randint(-1000, 1000) for _ in range(n1))
        b = sorted(rng.randint(-1000, 1000) for _ in range(n2))
        expected = sorted(a + b)

        it_out = to_list(merge_two_lists(build(a), build(b)))
        assert it_out == expected, f"iterative wrong: a={a}, b={b}, got={it_out}"
        assert is_sorted(it_out), "iterative output not sorted"

        rc_out = to_list(merge_two_lists_recursive(build(a), build(b)))
        assert rc_out == expected, f"recursive wrong: a={a}, b={b}, got={rc_out}"

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


# ----------------------------------------------------------------------
# 6. EDGE CASES
# ----------------------------------------------------------------------
def edge_cases() -> None:
    cases = [
        ([], [], "both empty"),
        ([], [0], "one empty"),
        ([1], [], "other empty"),
        ([1, 2, 4], [1, 3, 4], "canonical"),
        ([1, 1, 1], [1, 1, 1], "all equal — stability trap"),
        ([5], [1], "leftover-tail kicks in immediately"),
        ([-3, -1, 0], [-2, 2, 4], "negatives"),
        (list(range(0, 100, 2)), list(range(1, 100, 2)), "perfectly interleaved"),
    ]
    for a, b, label in cases:
        out = to_list(merge_two_lists(build(a), build(b)))
        expected = sorted(a + b)
        ok = out == expected and is_sorted(out)
        status = "PASS" if ok else "FAIL"
        sample = expected if len(expected) <= 10 else f"len={len(expected)}"
        print(f"  [{status}] {label}: expected={sample}")


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