"""
# 2. Add Two Numbers

## Problem
You are given two non-empty linked lists representing two non-negative integers.
The digits are stored in reverse order, and each of their nodes contains a single digit.
Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not have leading zeros, except the number 0 itself.

## Examples

```text
Input:  l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807

Input:  l1 = [0], l2 = [0]
Output: [0]

Input:  l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
```

## Constraints
- The number of nodes in each linked list is in the range [1, 100].
- 0 <= Node.val <= 9
- It is guaranteed that the list represents a number that does not have leading zeros.
"""
from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def build_list(vals):
    dummy = ListNode(0)
    curr = dummy
    for v in vals:
        curr.next = ListNode(v)
        curr = curr.next
    return dummy.next


def list_to_arr(head):
    arr = []
    while head:
        arr.append(head.val)
        head = head.next
    return arr


class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        # Simulate addition digit by digit with carry
        # Advance both lists simultaneously; handle remaining digits and final carry
        # O(max(m,n)) time, O(max(m,n)) space
        dummy = ListNode(0)
        curr = dummy
        carry = 0
        while l1 or l2 or carry:
            val = carry
            if l1:
                val += l1.val
                l1 = l1.next
            if l2:
                val += l2.val
                l2 = l2.next
            carry, digit = divmod(val, 10)
            curr.next = ListNode(digit)
            curr = curr.next
        return dummy.next


if __name__ == '__main__':
    s = Solution()

    assert list_to_arr(s.addTwoNumbers(build_list([2, 4, 3]), build_list([5, 6, 4]))) == [7, 0, 8]
    assert list_to_arr(s.addTwoNumbers(build_list([0]), build_list([0]))) == [0]
    assert list_to_arr(s.addTwoNumbers(
        build_list([9, 9, 9, 9, 9, 9, 9]),
        build_list([9, 9, 9, 9])
    )) == [8, 9, 9, 9, 0, 0, 0, 1]

    print("All tests passed.")

"""
# 138. Copy List with Random Pointer

## Problem
A linked list of length n is given such that each node contains an additional
random pointer, which could point to any node in the list, or null.
Construct a deep copy of the list. The deep copy should consist of exactly n
brand new nodes, where each new node has its value set to the value of its
corresponding original node. Both the next and random pointer of the new nodes
should point to new nodes in the copied list such that the pointers in the
original list and copied list represent the same list state.
None of the pointers in the new list should point to nodes in the original list.

## Examples

```text
Input:  head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Input:  head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Input:  head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]
```

## Constraints
- 0 <= n <= 1000
- -10^4 <= Node.val <= 10^4
- Node.random is null or pointing to some node in the linked list.
"""
from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Node:
    def __init__(self, x: int, next=None, random=None):
        self.val = int(x)
        self.next = next
        self.random = random


def build_list(vals):
    dummy = ListNode(0)
    curr = dummy
    for v in vals:
        curr.next = ListNode(v)
        curr = curr.next
    return dummy.next


def list_to_arr(head):
    arr = []
    while head:
        arr.append(head.val)
        head = head.next
    return arr


def build_random_list(data):
    """data: list of [val, random_index] where random_index is None or int."""
    if not data:
        return None
    nodes = [Node(d[0]) for d in data]
    for i, d in enumerate(data):
        if i < len(nodes) - 1:
            nodes[i].next = nodes[i + 1]
        if d[1] is not None:
            nodes[i].random = nodes[d[1]]
    return nodes[0]


class Solution:
    def copyRandomList_hashmap(self, head: 'Optional[Node]') -> 'Optional[Node]':
        # O(n) time, O(n) space
        if not head:
            return None
        old_to_new = {}
        curr = head
        while curr:
            old_to_new[curr] = Node(curr.val)
            curr = curr.next
        curr = head
        while curr:
            if curr.next:
                old_to_new[curr].next = old_to_new[curr.next]
            if curr.random:
                old_to_new[curr].random = old_to_new[curr.random]
            curr = curr.next
        return old_to_new[head]

    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        # First pass: create all new nodes and map old->new
        # Second pass: wire up next and random pointers using the map
        # O(n) time, O(1) space — interleave cloned nodes
        if not head:
            return None
        # Step 1: interleave clones
        curr = head
        while curr:
            clone = Node(curr.val, curr.next)
            curr.next = clone
            curr = clone.next
        # Step 2: assign random pointers
        curr = head
        while curr:
            if curr.random:
                curr.next.random = curr.random.next
            curr = curr.next.next
        # Step 3: separate lists
        dummy = Node(0)
        clone_curr = dummy
        curr = head
        while curr:
            clone_curr.next = curr.next
            curr.next = curr.next.next
            clone_curr = clone_curr.next
            curr = curr.next
        return dummy.next


if __name__ == '__main__':
    s = Solution()

    original = build_random_list([[7, None], [13, 0], [11, 4], [10, 2], [1, 0]])
    copy1 = s.copyRandomList_hashmap(original)
    assert copy1 is not original
    assert copy1.val == 7
    assert copy1.next.val == 13
    assert copy1.next.random.val == 7

    original2 = build_random_list([[7, None], [13, 0], [11, 4], [10, 2], [1, 0]])
    copy2 = s.copyRandomList(original2)
    assert copy2 is not original2
    assert copy2.val == 7
    assert copy2.next.random.val == 7

    assert s.copyRandomList(None) is None

    print("All tests passed.")

"""
# 622. Design Circular Queue

## Problem
Design your implementation of the circular queue. The circular queue is a linear
data structure in which the operations are performed based on FIFO principle, and
the last position is connected back to the first position to make a circle.
It is also called "Ring Buffer".

Implement the MyCircularQueue class:
- MyCircularQueue(k): Initializes the object with the size of the queue to be k.
- int Front(): Gets the front item from the queue. If the queue is empty, return -1.
- int Rear(): Gets the last item from the queue. If the queue is empty, return -1.
- boolean enQueue(int value): Inserts an element into the circular queue. Return true if successful.
- boolean deQueue(): Deletes an element from the circular queue. Return true if successful.
- boolean isEmpty(): Checks whether the circular queue is empty or not.
- boolean isFull(): Checks whether the circular queue is full or not.

## Examples

```text
Input:
  MyCircularQueue(3)
  enQueue(1) -> true
  enQueue(2) -> true
  enQueue(3) -> true
  enQueue(4) -> false  (queue is full)
  Rear()     -> 3
  isFull()   -> true
  deQueue()  -> true
  enQueue(4) -> true
  Rear()     -> 4
```

## Constraints
- 1 <= k <= 1000
- 0 <= value <= 1000
- At most 3000 calls will be made to enQueue, deQueue, Front, Rear, isEmpty, and isFull.
"""


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def build_list(vals):
    dummy = ListNode(0)
    curr = dummy
    for v in vals:
        curr.next = ListNode(v)
        curr = curr.next
    return dummy.next


def list_to_arr(head):
    arr = []
    while head:
        arr.append(head.val)
        head = head.next
    return arr


class MyCircularQueue:
    # O(1) time per operation, O(k) space — array with front/rear pointers

    def __init__(self, k: int):
        self.q = [0] * k
        self.front = 0
        self.size = 0
        self.capacity = k

    def enQueue(self, value: int) -> bool:
        # Add element at rear; advance rear pointer with wrap-around
        if self.isFull():
            return False
        rear = (self.front + self.size) % self.capacity
        self.q[rear] = value
        self.size += 1
        return True

    def deQueue(self) -> bool:
        # Remove element at front; advance front pointer with wrap-around
        if self.isEmpty():
            return False
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return True

    def Front(self) -> int:
        # Return element at front without removing it
        return -1 if self.isEmpty() else self.q[self.front]

    def Rear(self) -> int:
        # Return element at rear without removing it
        if self.isEmpty():
            return -1
        return self.q[(self.front + self.size - 1) % self.capacity]

    def isEmpty(self) -> bool:
        # Queue is empty when size is 0
        return self.size == 0

    def isFull(self) -> bool:
        # Queue is full when size equals capacity
        return self.size == self.capacity


if __name__ == '__main__':
    cq = MyCircularQueue(3)
    assert cq.enQueue(1) is True
    assert cq.enQueue(2) is True
    assert cq.enQueue(3) is True
    assert cq.enQueue(4) is False
    assert cq.Rear() == 3
    assert cq.isFull() is True
    assert cq.deQueue() is True
    assert cq.enQueue(4) is True
    assert cq.Rear() == 4
    assert cq.Front() == 2

    cq2 = MyCircularQueue(1)
    assert cq2.isEmpty() is True
    assert cq2.Front() == -1
    assert cq2.Rear() == -1
    assert cq2.enQueue(5) is True
    assert cq2.isFull() is True
    assert cq2.Front() == 5
    assert cq2.Rear() == 5

    print("All tests passed.")

"""
# 287. Find the Duplicate Number

## Problem
Given an array of integers nums containing n + 1 integers where each integer is
in the range [1, n] inclusive, there is only one repeated number in nums.
Return this repeated number.
You must solve the problem without modifying the array nums and uses only constant extra space.

## Examples

```text
Input:  nums = [1,3,4,2,2]
Output: 2

Input:  nums = [3,1,3,4,2]
Output: 3

Input:  nums = [3,3,3,3,3]
Output: 3
```

## Constraints
- 1 <= n <= 10^5
- nums.length == n + 1
- 1 <= nums[i] <= n
- All the integers in nums appear only once except for precisely one integer which appears two or more times.
"""
from typing import List


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def build_list(vals):
    dummy = ListNode(0)
    curr = dummy
    for v in vals:
        curr.next = ListNode(v)
        curr = curr.next
    return dummy.next


def list_to_arr(head):
    arr = []
    while head:
        arr.append(head.val)
        head = head.next
    return arr


class Solution:
    def findDuplicate_hashset(self, nums: List[int]) -> int:
        # O(n) time, O(n) space
        seen = set()
        for n in nums:
            if n in seen:
                return n
            seen.add(n)
        return -1

    def findDuplicate(self, nums: List[int]) -> int:
        # Treat array as a linked list: index -> nums[index]
        # Floyd's cycle detection finds the entry point of the cycle = duplicate
        # O(n) time, O(1) space — treat array as linked list, find cycle entry
        slow = fast = nums[0]
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break
        slow = nums[0]
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]
        return slow


if __name__ == '__main__':
    s = Solution()

    assert s.findDuplicate_hashset([1, 3, 4, 2, 2]) == 2
    assert s.findDuplicate_hashset([3, 1, 3, 4, 2]) == 3

    assert s.findDuplicate([1, 3, 4, 2, 2]) == 2
    assert s.findDuplicate([3, 1, 3, 4, 2]) == 3
    assert s.findDuplicate([3, 3, 3, 3, 3]) == 3

    print("All tests passed.")

"""
# 460. LFU Cache

## Problem
Design and implement a data structure for a Least Frequently Used (LFU) cache.

Implement the LFUCache class:
- LFUCache(int capacity): Initializes the object with the capacity of the data structure.
- int get(int key): Gets the value of the key if it exists in the cache. Otherwise, returns -1.
- void put(int key, int value): Update the value of the key if present, or inserts the key
  if not already present. When the cache reaches its capacity, it should invalidate and remove
  the least frequently used key before inserting a new item. For ties, the least recently used
  key among the least frequently used keys is removed.

Both get and put must run in O(1) average time complexity.

## Examples

```text
Input:
  LFUCache(2)
  put(1, 1)       freq: {1:1}
  put(2, 2)       freq: {1:1, 2:1}
  get(1)   -> 1   freq: {1:2, 2:1}
  put(3, 3)       evicts key 2, freq: {1:2, 3:1}
  get(2)   -> -1
  get(3)   -> 3   freq: {1:2, 3:2}
  put(4, 4)       evicts key 3 (or 1, both freq=2; 3 is LRU), freq: {1:2, 4:1}
  get(1)   -> 1
  get(3)   -> -1
  get(4)   -> 4
```

## Constraints
- 0 <= capacity <= 10^4
- 0 <= key <= 10^5
- 0 <= value <= 10^9
- At most 2 * 10^5 calls will be made to get and put.
"""
from collections import defaultdict, OrderedDict


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def build_list(vals):
    dummy = ListNode(0)
    curr = dummy
    for v in vals:
        curr.next = ListNode(v)
        curr = curr.next
    return dummy.next


def list_to_arr(head):
    arr = []
    while head:
        arr.append(head.val)
        head = head.next
    return arr


class LFUCache:
    # O(1) time per get/put — hash maps + OrderedDict per frequency bucket

    def __init__(self, capacity: int):
        self.cap = capacity
        self.min_freq = 0
        self.key_val = {}                          # key -> value
        self.key_freq = {}                         # key -> frequency
        self.freq_keys = defaultdict(OrderedDict)  # freq -> OrderedDict of keys (LRU order)

    def _update(self, key: int) -> None:
        freq = self.key_freq[key]
        del self.freq_keys[freq][key]
        if not self.freq_keys[freq] and freq == self.min_freq:
            self.min_freq += 1
        self.key_freq[key] = freq + 1
        self.freq_keys[freq + 1][key] = None

    def get(self, key: int) -> int:
        # Increment frequency of key, move to higher-freq bucket, return value
        if key not in self.key_val:
            return -1
        self._update(key)
        return self.key_val[key]

    def put(self, key: int, value: int) -> None:
        # If key exists, update value and increment frequency
        # If at capacity, evict the LFU key (least frequent, then least recent)
        # Insert new key with frequency 1; update min_freq to 1
        if self.cap == 0:
            return
        if key in self.key_val:
            self.key_val[key] = value
            self._update(key)
        else:
            if len(self.key_val) >= self.cap:
                evict_key, _ = self.freq_keys[self.min_freq].popitem(last=False)
                del self.key_val[evict_key]
                del self.key_freq[evict_key]
            self.key_val[key] = value
            self.key_freq[key] = 1
            self.freq_keys[1][key] = None
            self.min_freq = 1


if __name__ == '__main__':
    # Trace: cap=2
    # put(1,1): {1:v1,f1}  min=1
    # put(2,2): {1:v1,f1, 2:v2,f1}  min=1
    # get(1)->1: {1:v1,f2, 2:v2,f1}  min=1
    # put(3,3): evict LRU at min_freq=1 -> evict key 2; {1:v1,f2, 3:v3,f1}  min=1
    # get(2)->-1
    # get(3)->3: {1:v1,f2, 3:v3,f2}  min=2
    # put(4,4): evict LRU at min_freq=2 -> evict key 1 (inserted before 3 reached f2)
    #           {3:v3,f2, 4:v4,f1}  min=1
    # get(1)->-1, get(3)->3, get(4)->4
    c = LFUCache(2)
    c.put(1, 1)
    c.put(2, 2)
    assert c.get(1) == 1
    c.put(3, 3)
    assert c.get(2) == -1
    assert c.get(3) == 3
    c.put(4, 4)
    assert c.get(1) == -1
    assert c.get(3) == 3
    assert c.get(4) == 4

    c2 = LFUCache(0)
    c2.put(0, 0)
    assert c2.get(0) == -1

    print("All tests passed.")

"""
# 141. Linked List Cycle

## Problem
Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle if some node can be reached again by continuously following the next pointer.
Return true if there is a cycle, otherwise return false.

## Examples

```text
Input:  head = [3,2,0,-4], pos = 1   (tail connects to node at index 1)
Output: true

Input:  head = [1,2], pos = 0
Output: true

Input:  head = [1], pos = -1
Output: false
```

## Constraints
- The number of nodes in the list is in the range [0, 10^4].
- -10^5 <= Node.val <= 10^5
- pos is -1 or a valid index in the linked list.
"""
from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def build_list(vals):
    dummy = ListNode(0)
    curr = dummy
    for v in vals:
        curr.next = ListNode(v)
        curr = curr.next
    return dummy.next


def list_to_arr(head):
    arr = []
    while head:
        arr.append(head.val)
        head = head.next
    return arr


def build_cycle_list(vals, pos):
    """Build a list where tail.next points to node at index pos (-1 = no cycle)."""
    if not vals:
        return None
    nodes = [ListNode(v) for v in vals]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    if pos != -1:
        nodes[-1].next = nodes[pos]
    return nodes[0]


class Solution:
    def hasCycle_hashset(self, head: Optional[ListNode]) -> bool:
        # O(n) time, O(n) space
        seen = set()
        curr = head
        while curr:
            if id(curr) in seen:
                return True
            seen.add(id(curr))
            curr = curr.next
        return False

    def hasCycle(self, head: Optional[ListNode]) -> bool:
        # Floyd's cycle detection: slow moves 1 step, fast moves 2 steps
        # If they meet, there's a cycle; if fast reaches None, no cycle
        # O(n) time, O(1) space — two pointers
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                return True
        return False


if __name__ == '__main__':
    s = Solution()

    assert s.hasCycle_hashset(build_cycle_list([3, 2, 0, -4], 1)) is True
    assert s.hasCycle_hashset(build_cycle_list([1, 2], 0)) is True
    assert s.hasCycle_hashset(build_cycle_list([1], -1)) is False

    assert s.hasCycle(build_cycle_list([3, 2, 0, -4], 1)) is True
    assert s.hasCycle(build_cycle_list([1, 2], 0)) is True
    assert s.hasCycle(build_cycle_list([1], -1)) is False
    assert s.hasCycle(None) is False

    print("All tests passed.")

"""
# 146. LRU Cache

## Problem
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:
- LRUCache(int capacity): Initialize the LRU cache with positive size capacity.
- int get(int key): Return the value of the key if it exists, otherwise return -1.
- void put(int key, int value): Update the value of the key if it exists. Otherwise,
  add the key-value pair to the cache. If the number of keys exceeds the capacity,
  evict the least recently used key.

Both get and put must run in O(1) average time complexity.

## Examples

```text
Input:
  LRUCache(2)
  put(1, 1)       cache: {1=1}
  put(2, 2)       cache: {1=1, 2=2}
  get(1)   -> 1   cache: {2=2, 1=1}
  put(3, 3)       evicts key 2, cache: {1=1, 3=3}
  get(2)   -> -1
  put(4, 4)       evicts key 1, cache: {3=3, 4=4}
  get(1)   -> -1
  get(3)   -> 3
  get(4)   -> 4
```

## Constraints
- 1 <= capacity <= 3000
- 0 <= key <= 10^4
- 0 <= value <= 10^5
- At most 2 * 10^5 calls will be made to get and put.
"""
from collections import OrderedDict


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def build_list(vals):
    dummy = ListNode(0)
    curr = dummy
    for v in vals:
        curr.next = ListNode(v)
        curr = curr.next
    return dummy.next


def list_to_arr(head):
    arr = []
    while head:
        arr.append(head.val)
        head = head.next
    return arr


# ── Approach 1: OrderedDict ──────────────────────────────────────────────────

class LRUCache_OrderedDict:
    # O(1) time per get/put, O(capacity) space
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = OrderedDict()

    def get(self, key: int) -> int:
        # Move accessed node to tail (most recently used), return its value
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        # If key exists, remove old node; insert new node at tail
        # If over capacity, evict the LRU node at head.next
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)


# ── Approach 2: Doubly linked list + hash map ────────────────────────────────

class _DNode:
    __slots__ = ('key', 'val', 'prev', 'next')
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = self.next = None


class LRUCache:
    # O(1) time per get/put, O(capacity) space
    def __init__(self, capacity: int):
        self.cap = capacity
        self.map = {}
        self.head = _DNode()   # dummy head (LRU end)
        self.tail = _DNode()   # dummy tail (MRU end)
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node: _DNode) -> None:
        # Unlink node from doubly linked list by connecting its neighbors
        node.prev.next = node.next
        node.next.prev = node.prev

    def _insert_tail(self, node: _DNode) -> None:
        # Insert node just before the dummy tail (most recently used position)
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev.next = node
        self.tail.prev = node

    def get(self, key: int) -> int:
        # Move accessed node to tail (most recently used), return its value
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._insert_tail(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        # If key exists, remove old node; insert new node at tail
        # If over capacity, evict the LRU node at head.next
        if key in self.map:
            self._remove(self.map[key])
        node = _DNode(key, value)
        self.map[key] = node
        self._insert_tail(node)
        if len(self.map) > self.cap:
            lru = self.head.next
            self._remove(lru)
            del self.map[lru.key]


if __name__ == '__main__':
    for Cache in (LRUCache_OrderedDict, LRUCache):
        c = Cache(2)
        c.put(1, 1)
        c.put(2, 2)
        assert c.get(1) == 1
        c.put(3, 3)
        assert c.get(2) == -1
        c.put(4, 4)
        assert c.get(1) == -1
        assert c.get(3) == 3
        assert c.get(4) == 4

    print("All tests passed.")

"""
# 23. Merge K Sorted Lists

## Problem
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.

## Examples

```text
Input:  lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]

Input:  lists = []
Output: []

Input:  lists = [[]]
Output: []
```

## Constraints
- k == lists.length
- 0 <= k <= 10^4
- 0 <= lists[i].length <= 500
- -10^4 <= lists[i][j] <= 10^4
- lists[i] is sorted in ascending order.
- The sum of lists[i].length will not exceed 10^4.
"""
from typing import List, Optional
import heapq


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def build_list(vals):
    dummy = ListNode(0)
    curr = dummy
    for v in vals:
        curr.next = ListNode(v)
        curr = curr.next
    return dummy.next


def list_to_arr(head):
    arr = []
    while head:
        arr.append(head.val)
        head = head.next
    return arr


class Solution:
    def mergeKLists_sequential(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        # O(kN) time, O(1) space — merge one by one
        def merge_two(l1, l2):
            dummy = ListNode(0)
            curr = dummy
            while l1 and l2:
                if l1.val <= l2.val:
                    curr.next = l1; l1 = l1.next
                else:
                    curr.next = l2; l2 = l2.next
                curr = curr.next
            curr.next = l1 or l2
            return dummy.next

        result = None
        for lst in lists:
            result = merge_two(result, lst)
        return result

    def mergeKLists_divide(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        # O(N log k) time, O(log k) space — divide and conquer
        def merge_two(l1, l2):
            dummy = ListNode(0)
            curr = dummy
            while l1 and l2:
                if l1.val <= l2.val:
                    curr.next = l1; l1 = l1.next
                else:
                    curr.next = l2; l2 = l2.next
                curr = curr.next
            curr.next = l1 or l2
            return dummy.next

        if not lists:
            return None
        while len(lists) > 1:
            merged = []
            for i in range(0, len(lists), 2):
                l1 = lists[i]
                l2 = lists[i + 1] if i + 1 < len(lists) else None
                merged.append(merge_two(l1, l2))
            lists = merged
        return lists[0]

    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        # Use a min-heap to always extract the globally smallest node
        # Push each list's head; after popping, push that node's next
        # O(N log k) time, O(k) space — min heap
        heap = []
        for i, node in enumerate(lists):
            if node:
                heapq.heappush(heap, (node.val, i, node))
        dummy = ListNode(0)
        curr = dummy
        while heap:
            val, i, node = heapq.heappop(heap)
            curr.next = node
            curr = curr.next
            if node.next:
                heapq.heappush(heap, (node.next.val, i, node.next))
        return dummy.next


if __name__ == '__main__':
    s = Solution()

    def make(lists_vals):
        return [build_list(v) for v in lists_vals]

    expected = [1, 1, 2, 3, 4, 4, 5, 6]
    assert list_to_arr(s.mergeKLists_sequential(make([[1, 4, 5], [1, 3, 4], [2, 6]]))) == expected
    assert list_to_arr(s.mergeKLists_divide(make([[1, 4, 5], [1, 3, 4], [2, 6]]))) == expected
    assert list_to_arr(s.mergeKLists(make([[1, 4, 5], [1, 3, 4], [2, 6]]))) == expected

    assert s.mergeKLists([]) is None
    assert s.mergeKLists([None]) is None

    print("All tests passed.")

"""
# 21. Merge Two Sorted Lists

## Problem
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted list. The list should be made by splicing
together the nodes of the first two lists.
Return the head of the merged linked list.

## Examples

```text
Input:  list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Input:  list1 = [], list2 = []
Output: []

Input:  list1 = [], list2 = [0]
Output: [0]
```

## Constraints
- The number of nodes in both lists is in the range [0, 50].
- -100 <= Node.val <= 100
- Both list1 and list2 are sorted in non-decreasing order.
"""
from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def build_list(vals):
    dummy = ListNode(0)
    curr = dummy
    for v in vals:
        curr.next = ListNode(v)
        curr = curr.next
    return dummy.next


def list_to_arr(head):
    arr = []
    while head:
        arr.append(head.val)
        head = head.next
    return arr


class Solution:
    def mergeTwoLists_iterative(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        # Use a dummy head to simplify edge cases; always attach the smaller node
        # O(n+m) time, O(1) space
        dummy = ListNode(0)
        curr = dummy
        while list1 and list2:
            if list1.val <= list2.val:
                curr.next = list1
                list1 = list1.next
            else:
                curr.next = list2
                list2 = list2.next
            curr = curr.next
        curr.next = list1 or list2
        return dummy.next

    def mergeTwoLists_recursive(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        # O(n+m) time, O(n+m) space (call stack)
        if not list1:
            return list2
        if not list2:
            return list1
        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists_recursive(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists_recursive(list1, list2.next)
            return list2

    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        # Recursive: attach the smaller head and recurse on the rest
        return self.mergeTwoLists_iterative(list1, list2)


if __name__ == '__main__':
    s = Solution()

    assert list_to_arr(s.mergeTwoLists_iterative(build_list([1, 2, 4]), build_list([1, 3, 4]))) == [1, 1, 2, 3, 4, 4]
    assert list_to_arr(s.mergeTwoLists_recursive(build_list([1, 2, 4]), build_list([1, 3, 4]))) == [1, 1, 2, 3, 4, 4]
    assert s.mergeTwoLists(None, None) is None
    assert list_to_arr(s.mergeTwoLists(None, build_list([0]))) == [0]

    print("All tests passed.")

"""
# 19. Remove Nth Node From End of List

## Problem
Given the head of a linked list, remove the nth node from the end of the list
and return its head.

## Examples

```text
Input:  head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Input:  head = [1], n = 1
Output: []

Input:  head = [1,2], n = 1
Output: [1]
```

## Constraints
- The number of nodes in the list is sz.
- 1 <= sz <= 30
- 0 <= Node.val <= 100
- 1 <= n <= sz
"""
from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def build_list(vals):
    dummy = ListNode(0)
    curr = dummy
    for v in vals:
        curr.next = ListNode(v)
        curr = curr.next
    return dummy.next


def list_to_arr(head):
    arr = []
    while head:
        arr.append(head.val)
        head = head.next
    return arr


class Solution:
    def removeNthFromEnd_twopass(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        # O(n) time, O(1) space — two passes
        dummy = ListNode(0, head)
        length = 0
        curr = head
        while curr:
            length += 1
            curr = curr.next
        curr = dummy
        for _ in range(length - n):
            curr = curr.next
        curr.next = curr.next.next
        return dummy.next

    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        # Use two pointers n apart; when fast reaches end, slow is at the target
        # Dummy head handles edge case of removing the first node
        # O(n) time, O(1) space — one pass with two pointers
        dummy = ListNode(0, head)
        fast = dummy
        for _ in range(n + 1):
            fast = fast.next
        slow = dummy
        while fast:
            slow = slow.next
            fast = fast.next
        slow.next = slow.next.next
        return dummy.next


if __name__ == '__main__':
    s = Solution()

    assert list_to_arr(s.removeNthFromEnd_twopass(build_list([1, 2, 3, 4, 5]), 2)) == [1, 2, 3, 5]
    assert list_to_arr(s.removeNthFromEnd_twopass(build_list([1]), 1)) == []
    assert list_to_arr(s.removeNthFromEnd_twopass(build_list([1, 2]), 1)) == [1]

    assert list_to_arr(s.removeNthFromEnd(build_list([1, 2, 3, 4, 5]), 2)) == [1, 2, 3, 5]
    assert list_to_arr(s.removeNthFromEnd(build_list([1]), 1)) == []
    assert list_to_arr(s.removeNthFromEnd(build_list([1, 2]), 1)) == [1]

    print("All tests passed.")

"""
# 143. Reorder List

## Problem
You are given the head of a singly linked-list:
  L0 → L1 → … → Ln-1 → Ln
Reorder it to:
  L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
You may not modify the values in the list's nodes. Only nodes themselves may be changed.

## Examples

```text
Input:  head = [1,2,3,4]
Output: [1,4,2,3]

Input:  head = [1,2,3,4,5]
Output: [1,5,2,4,3]
```

## Constraints
- The number of nodes in the list is in the range [1, 5 * 10^4].
- 1 <= Node.val <= 1000
"""
from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def build_list(vals):
    dummy = ListNode(0)
    curr = dummy
    for v in vals:
        curr.next = ListNode(v)
        curr = curr.next
    return dummy.next


def list_to_arr(head):
    arr = []
    while head:
        arr.append(head.val)
        head = head.next
    return arr


class Solution:
    def reorderList_array(self, head: Optional[ListNode]) -> None:
        # O(n) time, O(n) space
        if not head:
            return
        nodes = []
        curr = head
        while curr:
            nodes.append(curr)
            curr = curr.next
        lo, hi = 0, len(nodes) - 1
        while lo < hi:
            nodes[lo].next = nodes[hi]
            lo += 1
            if lo == hi:
                break
            nodes[hi].next = nodes[lo]
            hi -= 1
        nodes[lo].next = None

    def reorderList(self, head: Optional[ListNode]) -> None:
        # Step 1: find middle using slow/fast pointers
        # Step 2: reverse the second half in-place
        # Step 3: merge first half and reversed second half alternately
        # O(n) time, O(1) space — find middle, reverse second half, merge
        if not head or not head.next:
            return
        # find middle
        slow, fast = head, head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        # reverse second half
        prev, curr = None, slow.next
        slow.next = None
        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        # merge
        first, second = head, prev
        while second:
            tmp1, tmp2 = first.next, second.next
            first.next = second
            second.next = tmp1
            first = tmp1
            second = tmp2


if __name__ == '__main__':
    s = Solution()

    head = build_list([1, 2, 3, 4])
    s.reorderList_array(head)
    assert list_to_arr(head) == [1, 4, 2, 3]

    head = build_list([1, 2, 3, 4, 5])
    s.reorderList_array(head)
    assert list_to_arr(head) == [1, 5, 2, 4, 3]

    head = build_list([1, 2, 3, 4])
    s.reorderList(head)
    assert list_to_arr(head) == [1, 4, 2, 3]

    head = build_list([1, 2, 3, 4, 5])
    s.reorderList(head)
    assert list_to_arr(head) == [1, 5, 2, 4, 3]

    print("All tests passed.")

"""
# 206. Reverse Linked List

## Problem
Given the head of a singly linked list, reverse the list, and return the reversed list.

## Examples

```text
Input:  head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Input:  head = [1,2]
Output: [2,1]

Input:  head = []
Output: []
```

## Constraints
- The number of nodes in the list is in the range [0, 5000].
- -5000 <= Node.val <= 5000
"""
from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def build_list(vals):
    dummy = ListNode(0)
    curr = dummy
    for v in vals:
        curr.next = ListNode(v)
        curr = curr.next
    return dummy.next


def list_to_arr(head):
    arr = []
    while head:
        arr.append(head.val)
        head = head.next
    return arr


class Solution:
    def reverseList_iterative(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Keep track of prev; for each node, point its next to prev, then advance
        # O(n) time, O(1) space
        prev, curr = None, head
        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        return prev

    def reverseList_recursive(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # O(n) time, O(n) space (call stack)
        if not head or not head.next:
            return head
        new_head = self.reverseList_recursive(head.next)
        head.next.next = head
        head.next = None
        return new_head

    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Recursive: reverse the rest of the list, then attach current node at end
        return self.reverseList_iterative(head)


if __name__ == '__main__':
    s = Solution()

    head = build_list([1, 2, 3, 4, 5])
    assert list_to_arr(s.reverseList_iterative(head)) == [5, 4, 3, 2, 1]

    head = build_list([1, 2, 3, 4, 5])
    assert list_to_arr(s.reverseList_recursive(head)) == [5, 4, 3, 2, 1]

    assert s.reverseList(None) is None

    head = build_list([1])
    assert list_to_arr(s.reverseList(head)) == [1]

    print("All tests passed.")

"""
# 92. Reverse Linked List II

## Problem
Given the head of a singly linked list and two integers left and right where
left <= right, reverse the nodes of the list from position left to position right,
and return the reversed list.

## Examples

```text
Input:  head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

Input:  head = [5], left = 1, right = 1
Output: [5]
```

## Constraints
- The number of nodes in the list is n.
- 1 <= n <= 500
- -500 <= Node.val <= 500
- 1 <= left <= right <= n
"""
from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def build_list(vals):
    dummy = ListNode(0)
    curr = dummy
    for v in vals:
        curr.next = ListNode(v)
        curr = curr.next
    return dummy.next


def list_to_arr(head):
    arr = []
    while head:
        arr.append(head.val)
        head = head.next
    return arr


class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        # Advance to the node just before position left
        # Reverse the sublist from left to right in-place
        # Reconnect the reversed segment back into the list
        # O(n) time, O(1) space — single pass with prev tracking
        dummy = ListNode(0, head)
        pre = dummy
        for _ in range(left - 1):
            pre = pre.next
        curr = pre.next
        for _ in range(right - left):
            nxt = curr.next
            curr.next = nxt.next
            nxt.next = pre.next
            pre.next = nxt
        return dummy.next


if __name__ == '__main__':
    s = Solution()

    assert list_to_arr(s.reverseBetween(build_list([1, 2, 3, 4, 5]), 2, 4)) == [1, 4, 3, 2, 5]
    assert list_to_arr(s.reverseBetween(build_list([5]), 1, 1)) == [5]
    assert list_to_arr(s.reverseBetween(build_list([1, 2, 3, 4, 5]), 1, 5)) == [5, 4, 3, 2, 1]
    assert list_to_arr(s.reverseBetween(build_list([3, 5]), 1, 2)) == [5, 3]

    print("All tests passed.")

"""
# 25. Reverse Nodes in k-Group

## Problem
Given the head of a linked list, reverse the nodes of the list k at a time,
and return the modified list.
k is a positive integer and is less than or equal to the length of the linked list.
If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as is.
You may not alter the values in the list's nodes, only nodes themselves may be changed.

## Examples

```text
Input:  head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]

Input:  head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]
```

## Constraints
- The number of nodes in the list is n.
- 1 <= k <= n <= 5000
- 0 <= Node.val <= 1000
"""
from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def build_list(vals):
    dummy = ListNode(0)
    curr = dummy
    for v in vals:
        curr.next = ListNode(v)
        curr = curr.next
    return dummy.next


def list_to_arr(head):
    arr = []
    while head:
        arr.append(head.val)
        head = head.next
    return arr


class Solution:
    def reverseKGroup_iterative(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # O(n) time, O(1) space
        dummy = ListNode(0, head)
        group_prev = dummy

        while True:
            # check if k nodes remain
            kth = group_prev
            for _ in range(k):
                kth = kth.next
                if not kth:
                    return dummy.next
            group_next = kth.next

            # reverse the group
            prev, curr = group_next, group_prev.next
            while curr != group_next:
                nxt = curr.next
                curr.next = prev
                prev = curr
                curr = nxt

            # reconnect
            tmp = group_prev.next
            group_prev.next = kth
            group_prev = tmp

        return dummy.next

    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # Check if k nodes remain; if not, leave as-is
        # Reverse k nodes, then recursively process the rest
        # Connect reversed segment's tail to the result of the recursive call
        # O(n) time, O(n/k) space (recursion)
        curr = head
        count = 0
        while curr and count < k:
            curr = curr.next
            count += 1
        if count < k:
            return head
        # reverse k nodes
        prev, curr = None, head
        for _ in range(k):
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        # head is now the tail of reversed group; recurse for rest
        head.next = self.reverseKGroup(curr, k)
        return prev


if __name__ == '__main__':
    s = Solution()

    assert list_to_arr(s.reverseKGroup_iterative(build_list([1, 2, 3, 4, 5]), 2)) == [2, 1, 4, 3, 5]
    assert list_to_arr(s.reverseKGroup_iterative(build_list([1, 2, 3, 4, 5]), 3)) == [3, 2, 1, 4, 5]
    assert list_to_arr(s.reverseKGroup_iterative(build_list([1, 2, 3, 4, 5]), 1)) == [1, 2, 3, 4, 5]

    assert list_to_arr(s.reverseKGroup(build_list([1, 2, 3, 4, 5]), 2)) == [2, 1, 4, 3, 5]
    assert list_to_arr(s.reverseKGroup(build_list([1, 2, 3, 4, 5]), 3)) == [3, 2, 1, 4, 5]
    assert list_to_arr(s.reverseKGroup(build_list([1, 2, 3, 4, 5]), 1)) == [1, 2, 3, 4, 5]

    print("All tests passed.")