2. Add Two Numbers☆

// Definition for singly-linked list.
class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

function addTwoNumbers(
  l1: ListNode | null,
  l2: ListNode | null
): ListNode | null {
  const dummy = new ListNode(0);   // sentinel head — avoids edge-case for first node
  let cur = dummy;
  let carry = 0;

  while (l1 !== null || l2 !== null || carry !== 0) {
    const d1 = l1?.val ?? 0;      // treat an exhausted list as supplying 0
    const d2 = l2?.val ?? 0;
    const sum = d1 + d2 + carry;

    cur.next = new ListNode(sum % 10);   // append the ones digit
    carry = Math.floor(sum / 10);        // propagate the tens digit

    cur = cur.next;
    if (l1) l1 = l1.next;
    if (l2) l2 = l2.next;
  }

  return dummy.next;   // skip the sentinel
}

class LRUCache {
  private capacity: number;
  private map: Map<number, DLLNode>;
  private head: DLLNode; // dummy MRU sentinel
  private tail: DLLNode; // dummy LRU sentinel

  constructor(capacity: number) {
    this.capacity = capacity;
    this.map = new Map();
    this.head = new DLLNode(0, 0);
    this.tail = new DLLNode(0, 0);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  get(key: number): number {
    if (!this.map.has(key)) return -1;
    const node = this.map.get(key)!;
    this.remove(node);
    this.insertFront(node);
    return node.val;
  }

  put(key: number, value: number): void {
    if (this.map.has(key)) {
      const node = this.map.get(key)!;
      node.val = value;
      this.remove(node);
      this.insertFront(node);
    } else {
      const node = new DLLNode(key, value);
      this.map.set(key, node);
      this.insertFront(node);
      if (this.map.size > this.capacity) {
        const lru = this.tail.prev!;
        this.remove(lru);
        this.map.delete(lru.key);
      }
    }
  }

  private remove(node: DLLNode): void {
    node.prev!.next = node.next;
    node.next!.prev = node.prev;
  }

  private insertFront(node: DLLNode): void {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next!.prev = node;
    this.head.next = node;
  }
}

class DLLNode {
  key: number;
  val: number;
  prev: DLLNode | null = null;
  next: DLLNode | null = null;
  constructor(key: number, val: number) {
    this.key = key;
    this.val = val;
  }
}

// Definition: class ListNode { val: number; next: ListNode | null; ... }

function mergeTwoLists(
  list1: ListNode | null,
  list2: ListNode | null,
): ListNode | null {
  const dummy = new ListNode(0);   // sentinel avoids special-casing the head
  let tail: ListNode = dummy;

  while (list1 !== null && list2 !== null) {
    if (list1.val <= list2.val) {
      tail.next = list1;
      list1 = list1.next;
    } else {
      tail.next = list2;
      list2 = list2.next;
    }
    tail = tail.next!;             // advance tail to the node just attached
  }

  // At most one list still has nodes — splice the remainder directly
  tail.next = list1 ?? list2;

  return dummy.next;               // skip the sentinel
}

// Definition for singly-linked list.
class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

// --- Approach 1: Divide & Conquer (matches the visualizer) ---
function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  if (lists.length === 0) return null;

  // Repeatedly halve the list of lists, merging pairs each round
  let current = lists.slice();
  while (current.length > 1) {
    const next: Array<ListNode | null> = [];
    for (let i = 0; i < current.length; i += 2) {
      if (i + 1 < current.length) {
        next.push(mergeTwoLists(current[i], current[i + 1]));
      } else {
        next.push(current[i]); // odd list — carry it over
      }
    }
    current = next;
  }
  return current[0];
}

function mergeTwoLists(
  a: ListNode | null,
  b: ListNode | null,
): ListNode | null {
  const dummy = new ListNode(0);
  let tail = dummy;
  while (a !== null && b !== null) {
    if (a.val <= b.val) { tail.next = a; a = a.next; }
    else                 { tail.next = b; b = b.next; }
    tail = tail.next!;
  }
  tail.next = a ?? b;
  return dummy.next;
}

// --- Approach 2: Min-Heap (O(N log k)) ---
// import { MinHeap } from 'some-heap-library'; // or implement manually
//
// function mergeKListsHeap(lists: Array<ListNode | null>): ListNode | null {
//   const heap = new MinHeap<ListNode>((a, b) => a.val - b.val);
//   for (const head of lists) if (head) heap.push(head);
//   const dummy = new ListNode(0);
//   let tail = dummy;
//   while (!heap.isEmpty()) {
//     const node = heap.pop()!;
//     tail.next = node;
//     tail = tail.next;
//     if (node.next) heap.push(node.next);
//   }
//   return dummy.next;
// }