/**
 * LC46 全排列（输入无重复数字）
 * @param {number[]} nums
 * @return {number[][]}
 */
function permute(nums) {
  const res = [];
  const n = nums.length;
  if (n === 0) return [[]];          // 边界：空输入返回 [[]]（空排列本身是一个解）

  const path = [];
  const used = new Array(n).fill(false);

  const backtrack = () => {
    if (path.length === n) {
      res.push([...path]);           // 必须拷贝！path 是同一个引用，会被后续回溯改掉
      return;
    }
    for (let i = 0; i < n; i++) {
      if (used[i]) continue;         // 该下标已在当前路径中
      used[i] = true;                // 做选择
      path.push(nums[i]);
      backtrack();                   // 进入下一层
      path.pop();                    // 撤销选择
      used[i] = false;
    }
  };

  backtrack();
  return res;
}

/**
 * LC47 全排列 II（输入含重复数字，结果不能有重复排列）
 * @param {number[]} nums
 * @return {number[][]}
 */
function permuteUnique(nums) {
  const res = [];
  const n = nums.length;
  if (n === 0) return [[]];

  // 关键第一步：排序，让相同元素相邻，才能用「相邻比较」剪枝
  nums.sort((a, b) => a - b);

  const path = [];
  const used = new Array(n).fill(false);

  const backtrack = () => {
    if (path.length === n) {
      res.push([...path]);
      return;
    }
    for (let i = 0; i < n; i++) {
      if (used[i]) continue;
      // 同层去重：前一个相同的数「在本层刚被撤销」，说明这条分支已经走过
      if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue;

      used[i] = true;
      path.push(nums[i]);
      backtrack();
      path.pop();
      used[i] = false;
    }
  };

  backtrack();
  return res;
}

// 自查
// permute([])         -> [[]]
// permute([1])        -> 1
// permute([1,2,3])    -> 6 个
// permuteUnique([1,1,2]) -> [[1,1,2],[1,2,1],[2,1,1]]  （3 个，不是 6 个）
// permuteUnique([1,1,1]) -> 1,1,1                  （1 个）

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

/**
 * LC198 打家劫舍（线性）—— 滚动变量版，O(1) 空间
 */
function rob(nums) {
  if (!nums || nums.length === 0) return 0;   // 边界：空数组
  let prev2 = 0;   // dp[i-2]
  let prev1 = 0;   // dp[i-1]
  for (const num of nums) {
    // 当前最优 = max(不偷这间, 偷这间)
    const cur = Math.max(prev1, prev2 + num);
    prev2 = prev1;
    prev1 = cur;
  }
  return prev1;
}

/**
 * LC213 打家劫舍 II（环形）
 */
function robCircle(nums) {
  if (!nums || nums.length === 0) return 0;
  const n = nums.length;
  if (n === 1) return nums[0];                // 关键边界：只有一间房，环退化成点
  if (n === 2) return Math.max(nums[0], nums[1]);

  // 在闭区间 [start, end] 上跑线性版
  const robRange = (start, end) => {
    let prev2 = 0, prev1 = 0;
    for (let i = start; i <= end; i++) {
      const cur = Math.max(prev1, prev2 + nums[i]);
      prev2 = prev1;
      prev1 = cur;
    }
    return prev1;
  };

  // A：不偷最后一间；B：不偷第一间
  return Math.max(robRange(0, n - 2), robRange(1, n - 1));
}

// 自查
// rob([])          -> 0
// rob([5])         -> 5
// rob([2,1,1,2])   -> 4   （偷 0 和 3）
// robCircle([2])   -> 2
// robCircle([2,3,2]) -> 3 （不能偷首尾的 2+2）
// robCircle([1,2,3,1]) -> 4

/** 二叉树节点 */
// function TreeNode(val, left, right) { this.val = val; this.left = left; this.right = right; }

/**
 * LC101 对称二叉树 —— 递归版
 */
function isSymmetric(root) {
  if (!root) return true;              // 边界：空树视为对称

  // 判断 p 与 q 是否互为镜像
  const isMirror = (p, q) => {
    if (!p && !q) return true;         // 同时为空 -> 镜像
    if (!p || !q) return false;        // 一空一非空 -> 不镜像
    if (p.val !== q.val) return false; // 值不等 -> 不镜像
    // 交叉递归：外侧对外侧，内侧对内侧
    return isMirror(p.left, q.right) && isMirror(p.right, q.left);
  };

  return isMirror(root.left, root.right);
}

/**
 * LC101 迭代版 —— 用队列成对比较（面试官常追问"不用递归怎么写"）
 */
function isSymmetricIterative(root) {
  if (!root) return true;
  const queue = [root.left, root.right];   // 成对入队

  while (queue.length) {
    const p = queue.shift();
    const q = queue.shift();

    if (!p && !q) continue;                // 这一对都空，跳过继续
    if (!p || !q || p.val !== q.val) return false;

    // 注意入队顺序：外侧一对，内侧一对
    queue.push(p.left, q.right);
    queue.push(p.right, q.left);
  }
  return true;
}

// 自查
// null                      -> true
// [1]                       -> true
// [1,2,2,3,4,4,3]           -> true
// [1,2,2,null,3,null,3]     -> false （结构不镜像）
// [1,2,2,2,null,2]          -> false

/**
 * 解法一：BFS 层序遍历，取每层最后一个节点
 */
function rightSideView(root) {
  const res = [];
  if (!root) return res;                 // 边界：空树返回 []

  const queue = [root];
  while (queue.length) {
    const size = queue.length;           // 锁定当前层的节点数（必须先存，循环里会变）
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      if (i === size - 1) res.push(node.val);  // 当前层最后一个 = 最右
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
  return res;
}

/**
 * 解法二：DFS 先右后左，depth === res.length 时记录
 * 原理：根->右->左 的遍历顺序保证每层最右节点被最先访问到
 */
function rightSideViewDFS(root) {
  const res = [];

  const dfs = (node, depth) => {
    if (!node) return;
    // 首次到达这个深度 —— 由于先右后左，它必是该层最右节点
    if (depth === res.length) res.push(node.val);
    dfs(node.right, depth + 1);          // 关键：先右
    dfs(node.left, depth + 1);           // 再左
  };

  dfs(root, 0);
  return res;
}

// 自查
// null              -> []
// [1]               -> [1]
// [1,2,3,null,5,null,4] -> [1,3,4]
// [1,2,null,3]      -> [1,2,3]  （全是左斜链，左节点也会被看到 —— 常见误解点）

/**
 * 解法一：哈希计数（通用，不要求有序）
 * @param {number[][]} arrays
 * @return {number[]}
 */
function intersectionByHash(arrays) {
  if (!arrays || arrays.length === 0) return [];
  if (arrays.length === 1) return [...new Set(arrays[0])];
  const k = arrays.length;

  const count = new Map();      // value -> 出现在多少个数组中
  const lastSeen = new Map();   // value -> 上一次贡献计数的数组下标（防同数组内重复重复计数）

  for (let i = 0; i < k; i++) {
    if (!arrays[i] || arrays[i].length === 0) return []; // 任一数组为空，交集必空
    for (const v of arrays[i]) {
      if (lastSeen.get(v) === i) continue;   // 同一数组里重复出现，只算一次
      lastSeen.set(v, i);
      count.set(v, (count.get(v) || 0) + 1);
    }
  }

  const res = [];
  for (const [v, c] of count) if (c === k) res.push(v);
  return res.sort((a, b) => a - b);
}

/**
 * 解法二：k 路指针（利用有序，额外空间 O(k)，不含输出）
 * 内部用「指数跳跃 + 二分」推进指针
 */
function intersectionSorted(arrays) {
  if (!arrays || arrays.length === 0) return [];
  const k = arrays.length;
  for (const a of arrays) {
    if (!a || a.length === 0) return [];    // 边界：任一为空 -> 交集为空
  }
  if (k === 1) {                            // 边界：只有一个数组 -> 自身去重
    const out = [];
    for (const v of arrays[0]) if (out[out.length - 1] !== v) out.push(v);
    return out;
  }

  const ptr = new Array(k).fill(0);         // 唯一的额外空间：k 个下标
  const res = [];

  /**
   * 在有序数组 arr 的 [from, arr.length) 中，找到第一个 >= target 的下标
   * 指数跳跃(galloping)探路 + 区间二分，稠密数据近似 O(1)，稀疏数据 O(log n)
   */
  const advanceTo = (arr, from, target) => {
    const n = arr.length;
    if (from >= n) return n;
    if (arr[from] >= target) return from;   // 已经满足，不用动

    let step = 1;
    let lo = from;
    let hi = from + step;
    while (hi < n && arr[hi] < target) {    // 倍增探路
      lo = hi;
      step <<= 1;
      hi = from + step;
    }
    hi = Math.min(hi, n - 1);

    // 在 (lo, hi] 上二分找第一个 >= target
    let left = lo + 1, right = hi;
    while (left <= right) {
      const mid = (left + right) >> 1;
      if (arr[mid] >= target) right = mid - 1;
      else left = mid + 1;
    }
    return left;                            // left 可能等于 n，表示走到头了
  };

  outer: while (true) {
    // 1) 求当前所有指针指向值的最大值
    let maxVal = -Infinity;
    for (let i = 0; i < k; i++) {
      if (ptr[i] >= arrays[i].length) break outer;   // 有数组走完了，直接结束
      if (arrays[i][ptr[i]] > maxVal) maxVal = arrays[i][ptr[i]];
    }

    // 2) 把所有 < maxVal 的指针推进到 >= maxVal
    let allEqual = true;
    for (let i = 0; i < k; i++) {
      if (arrays[i][ptr[i]] < maxVal) {
        ptr[i] = advanceTo(arrays[i], ptr[i], maxVal);
        if (ptr[i] >= arrays[i].length) break outer;
        allEqual = false;                   // 推进过，说明本轮还没对齐
      }
    }

    // 3) 全部对齐到同一个值 -> 命中交集
    if (allEqual) {
      res.push(maxVal);
      for (let i = 0; i < k; i++) {
        // 跳过该数组内所有等于 maxVal 的重复元素，保证结果去重
        while (ptr[i] < arrays[i].length && arrays[i][ptr[i]] === maxVal) ptr[i]++;
        if (ptr[i] >= arrays[i].length) break outer;
      }
    }
  }

  return res;
}

// 自查
// intersectionSorted([])                        -> []
// intersectionSorted(1,2,3)                 -> [1,2,3]
// intersectionSorted([[1,2,3],[]])              -> []
// intersectionSorted([[1,2,2,3],[2,2,4],[0,2,9]]) -> [2]   （重复值只出一次）
// intersectionSorted([[1,2],[3,4]])             -> []
// intersectionSorted([[1,5,100],[1,2,3,...,100]]) -> 跳跃前进优势明显

/**
 * LC162 寻找峰值 —— 二分，O(log n)
 * 不变式：[left, right] 内一定存在峰值
 */
function findPeakElement(nums) {
  if (!nums || nums.length === 0) return -1;  // 边界：空数组（LC 保证非空，但面试要提）
  let left = 0;
  let right = nums.length - 1;                // 单元素时 left === right，直接返回 0

  while (left < right) {
    const mid = left + ((right - left) >> 1); // 防溢出写法（JS 其实不会溢出，但体现习惯）
    if (nums[mid] < nums[mid + 1]) {
      // 上坡：峰在右半（mid 本身不可能是峰，可以安全丢掉）
      left = mid + 1;
    } else {
      // 下坡：峰在左半，mid 本身可能就是峰，所以不能 mid - 1
      right = mid;
    }
  }
  return left;   // left === right，即为峰值下标
}

// 自查
// []            -> -1
// [1]           -> 0        （单元素，左右都是 -∞）
// [1,2]         -> 1
// [2,1]         -> 0
// [1,2,3,1]     -> 2
// [1,2,1,3,5,6,4] -> 1 或 5（任意一个都算对）
// 严格递增 [1,2,3,4,5] -> 4（最后一个）

/**
 * 版本一：非原地简洁版（展示分治思路用）
 * 空间 O(n log n)，不适合大数据
 */
function quickSortSimple(arr) {
  if (!arr || arr.length <= 1) return arr;   // 边界：空数组 / 单元素直接返回

  const pivot = arr[arr.length >> 1];        // 取中间元素当基准
  const less = [], equal = [], greater = [];

  // 分成三份，把「等于 pivot」单独拎出来 —— 可以避免全相同元素时的死递归
  for (const x of arr) {
    if (x < pivot) less.push(x);
    else if (x > pivot) greater.push(x);
    else equal.push(x);
  }

  return [...quickSortSimple(less), ...equal, ...quickSortSimple(greater)];
}

/**
 * 版本二：原地分区版（Lomuto 分区 + 随机化 pivot）—— 面试标准答案
 * @param {number[]} arr 会被原地修改
 */
function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (!arr) return arr;
  while (lo < hi) {                          // 用 while + 尾递归消除，控制递归深度
    const p = partition(arr, lo, hi);
    // 先递归「较短」的一侧，另一侧用循环处理 -> 递归深度稳定 O(log n)
    if (p - lo < hi - p) {
      quickSort(arr, lo, p - 1);
      lo = p + 1;
    } else {
      quickSort(arr, p + 1, hi);
      hi = p - 1;
    }
  }
  return arr;
}

/**
 * Lomuto 分区：把 arr[lo..hi] 按 pivot 划分，返回 pivot 最终落位的下标
 * 分区后：[lo, i-1] 都 < pivot，i 是 pivot，[i+1, hi] 都 >= pivot
 */
function partition(arr, lo, hi) {
  // 随机化：避免有序输入退化成 O(n^2)
  const r = lo + Math.floor(Math.random() * (hi - lo + 1));
  [arr[r], arr[hi]] = [arr[hi], arr[r]];     // 把随机基准换到末尾

  const pivot = arr[hi];
  let i = lo;                                // i 指向「下一个小于 pivot 的元素该放的位置」
  for (let j = lo; j < hi; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[hi]] = [arr[hi], arr[i]];     // 基准归位
  return i;
}

// 自查
// quickSort([])            -> []
// quickSort([1])           -> [1]
// quickSort([2,2,2,2])     -> [2,2,2,2]  （全重复，随机 pivot 下不会退化太惨）
// quickSort([5,4,3,2,1])   -> [1,2,3,4,5]（逆序，随机化保证不爆栈）
// quickSort([3,-1,0,-1,9]) -> [-1,-1,0,3,9]（含负数、重复）

/** 链表节点 */
function ListNode(val, next = null) {
  this.val = val;
  this.next = next;
}

/**
 * LC148 链表排序 —— 自顶向下归并
 * @param {ListNode} head
 * @return {ListNode}
 */
function sortList(head) {
  // 递归出口：空链表 或 只有一个节点，已经有序
  if (!head || !head.next) return head;

  // ---- 1. 快慢指针找中点，并把链表从中间断开 ----
  let slow = head;
  let fast = head.next;          // fast 先走一步：保证偶数长度时 slow 落在「左半段的最后一个」
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  const mid = slow.next;         // 右半段的头
  slow.next = null;              // 关键！断开，否则递归无法收敛（死循环 / 爆栈）

  // ---- 2. 递归排序两半 ----
  const left = sortList(head);
  const right = sortList(mid);

  // ---- 3. 合并 ----
  return mergeTwo(left, right);
}

/**
 * 合并两个有序链表（dummy 节点消除头节点特判）
 */
function mergeTwo(l1, l2) {
  const dummy = new ListNode(0);   // 哨兵：让「接第一个节点」和「接后续节点」逻辑一致
  let tail = dummy;

  while (l1 && l2) {
    if (l1.val <= l2.val) {        // 用 <= 保证稳定性（相等时 l1 在前）
      tail.next = l1;
      l1 = l1.next;
    } else {
      tail.next = l2;
      l2 = l2.next;
    }
    tail = tail.next;
  }
  tail.next = l1 || l2;            // 剩下的一整段直接接上，不用逐个搬
  return dummy.next;
}

/* ============ ACM 格式：输入输出模板（腾讯笔试/实习面试常见） ============ */
/*
输入示例（一行空格分隔）：
4 2 1 3
输出：
1 2 3 4
*/
function main(input) {
  const nums = input.trim().split(/\s+/).filter(Boolean).map(Number);
  if (nums.length === 0) return '';          // 边界：空输入

  // 数组 -> 链表
  const dummy = new ListNode(0);
  let cur = dummy;
  for (const v of nums) {
    cur.next = new ListNode(v);
    cur = cur.next;
  }

  const sorted = sortList(dummy.next);

  // 链表 -> 输出字符串
  const out = [];
  for (let p = sorted; p; p = p.next) out.push(p.val);
  return out.join(' ');
}

// Node.js ACM 读入方式（牛客/腾讯笔试环境）
// const readline = require('readline');
// const rl = readline.createInterface({ input: process.stdin });
// rl.on('line', line => { console.log(main(line)); });

// 自查
// sortList(null)          -> null
// sortList([1])           -> [1]
// sortList([2,1])         -> [1,2]      （偶数长度，验证 fast=head.next 的必要性）
// sortList([3,3,3])       -> [3,3,3]    （全重复）
// sortList([-1,5,3,4,0])  -> [-1,0,3,4,5]

/* ---------- 方案 ①：排序 ---------- */
function topKBySort(nums, k) {
  if (!nums || k <= 0) return [];
  if (k >= nums.length) return [...nums].sort((a, b) => b - a);
  return [...nums].sort((a, b) => b - a).slice(0, k);   // 拷贝一份，不污染原数组
}

/* ---------- 方案 ②：手写小顶堆，维护大小为 k ---------- */
/**
 * 最小堆（数组实现的完全二叉树）
 * 父节点下标 i，左孩子 2i+1，右孩子 2i+2；孩子 i 的父亲 (i-1)>>1
 */
class MinHeap {
  constructor() {
    this.data = [];
  }
  size() { return this.data.length; }
  peek() { return this.data[0]; }

  push(val) {
    this.data.push(val);
    this._siftUp(this.data.length - 1);
  }

  pop() {
    if (this.data.length === 0) return undefined;
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length > 0) {
      this.data[0] = last;      // 把最后一个搬到堆顶，再下沉
      this._siftDown(0);
    }
    return top;
  }

  /** 替换堆顶（比 pop + push 少一次调整，Top-K 场景常用） */
  replaceTop(val) {
    this.data[0] = val;
    this._siftDown(0);
  }

  _siftUp(i) {
    const d = this.data;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (d[p] <= d[i]) break;              // 父节点更小，满足小顶堆性质，停止
      [d[p], d[i]] = [d[i], d[p]];
      i = p;
    }
  }

  _siftDown(i) {
    const d = this.data;
    const n = d.length;
    while (true) {
      const l = 2 * i + 1, r = 2 * i + 2;
      let min = i;
      if (l < n && d[l] < d[min]) min = l;
      if (r < n && d[r] < d[min]) min = r;
      if (min === i) break;                 // 已经比两个孩子都小
      [d[min], d[i]] = [d[i], d[min]];
      i = min;
    }
  }
}

/**
 * 小顶堆求最大的 K 个数 —— O(n log k)，空间 O(k)
 * 适用：k << n，或数据是流式的
 */
function topKByHeap(nums, k) {
  if (!nums || k <= 0) return [];
  const heap = new MinHeap();

  for (const num of nums) {
    if (heap.size() < k) {
      heap.push(num);                       // 前 k 个直接进堆
    } else if (num > heap.peek()) {
      heap.replaceTop(num);                 // 比堆里最小的还大 -> 顶掉它
    }
    // 否则：比 k 个候选里最小的还小，直接丢弃
  }

  // 堆里就是最大的 k 个（无序）；若要降序输出再排一次 O(k log k)
  return heap.data.slice().sort((a, b) => b - a);
}

/* ---------- 方案 ③：快速选择，平均 O(n) ---------- */
/**
 * 快速选择求最大的 K 个数 —— 平均 O(n)
 * 会原地打乱数组
 */
function topKByQuickSelect(nums, k) {
  if (!nums || k <= 0) return [];
  const arr = [...nums];                    // 拷贝，避免污染入参
  const n = arr.length;
  if (k >= n) return arr.sort((a, b) => b - a);

  const target = n - k;                     // 升序排列后，下标 [target, n-1] 就是最大的 k 个
  let lo = 0, hi = n - 1;

  while (lo < hi) {
    const p = partition(arr, lo, hi);
    if (p === target) break;
    if (p < target) lo = p + 1;             // 目标在右侧，丢掉左半
    else hi = p - 1;                        // 目标在左侧，丢掉右半
  }

  return arr.slice(target).sort((a, b) => b - a);
}

/** 随机化 Lomuto 分区（同第 7 题） */
function partition(arr, lo, hi) {
  const r = lo + Math.floor(Math.random() * (hi - lo + 1));
  [arr[r], arr[hi]] = [arr[hi], arr[r]];
  const pivot = arr[hi];
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[hi]] = [arr[hi], arr[i]];
  return i;
}

// 自查（三种方案结果应一致）
// topKByHeap([], 3)              -> []
// topKByHeap([1,2,3], 0)         -> []
// topKByHeap([5], 3)             -> [5]        （k > n）
// topKByHeap([3,3,3,3], 2)       -> [3,3]      （全重复）
// topKByHeap([3,2,1,5,6,4], 2)   -> [6,5]
// topKByQuickSelect([-1,-5,-3], 2) -> [-1,-3]  （全负数）

/**
 * 通用解：m 张试纸、n 个候选人，最坏情况最少检测次数
 * dp[k][m] = 用 m 张试纸、检测 k 次，最多能确定多少人
 * 转移：dp[k][m] = dp[k-1][m-1]   （这次阳性，试纸报废，往「上一段」查）
 *                + dp[k-1][m]     （这次阴性，试纸保留，往「后面」查）
 *                + 1              （本次混检覆盖的分界点本身）
 * 与 LC887「鸡蛋掉落」同构
 */
function minTests(n, m) {
  if (n <= 0) return 0;          // 边界：没人要测
  if (m <= 0) return Infinity;   // 边界：没试纸，无解
  if (m === 1) return n;         // 只有 1 张试纸，只能逐个线性测（最坏 n 次）

  const dp = new Array(m + 1).fill(0);   // dp[j] = 当前次数下、用 j 张试纸能覆盖的人数
  let k = 0;
  while (dp[m] < n) {
    k++;
    // 必须从后往前更新，保证 dp[j-1] 用的是「上一轮 k-1」的值
    for (let j = m; j >= 1; j--) {
      dp[j] = dp[j - 1] + dp[j] + 1;
    }
  }
  return k;
}

// 自查
// minTests(100, 2)  -> 14   （2 张试纸 100 人，双蛋模型）
// minTests(100, 1)  -> 100  （只有 1 张、阳性即废 -> 只能线性）
// minTests(0, 2)    -> 0
// minTests(1, 2)    -> 1
// minTests(105, 2)  -> 14   （k(k+1)/2 = 105 恰好卡满）
// minTests(106, 2)  -> 15
// minTests(1000, 10) -> 10  （试纸够多时退化为纯二分 log2(1000)≈10）

/**
 * 解读 A 的模拟：试纸可复用时的二分混检
 */
function binaryGroupTest(people, isPositive) {
  let lo = 0, hi = people.length - 1, count = 0;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    count++;
    // 混检 [lo, mid] 这一组
    if (isPositive(people.slice(lo, mid + 1))) hi = mid;
    else lo = mid + 1;
  }
  return { index: lo, tests: count };   // 100 人时 tests === 7
}

/**
 * 冒泡排序：相邻两两比较交换，每轮把最大的「冒」到末尾
 * 优化：一轮没发生交换 -> 已有序，提前退出（对近乎有序数据 O(n)）
 */
function bubbleSort(arr) {
  const a = [...arr];
  const n = a.length;
  if (n <= 1) return a;                       // 边界

  for (let i = 0; i < n - 1; i++) {
    let swapped = false;
    // 每轮结束后末尾 i 个元素已就位，无需再比
    for (let j = 0; j < n - 1 - i; j++) {
      if (a[j] > a[j + 1]) {                  // 严格大于才交换 -> 相等不动 -> 稳定
        [a[j], a[j + 1]] = [a[j + 1], a[j]];
        swapped = true;
      }
    }
    if (!swapped) break;                      // 本轮无交换，已经有序
  }
  return a;
}

/**
 * 选择排序：每轮从未排序区选出最小值，放到已排序区末尾
 * 不稳定！例：[5a, 5b, 1] -> 第一轮 5a 与 1 交换 -> [1, 5b, 5a]，5a/5b 顺序被打乱
 */
function selectionSort(arr) {
  const a = [...arr];
  const n = a.length;
  if (n <= 1) return a;

  for (let i = 0; i < n - 1; i++) {
    let minIdx = i;
    for (let j = i + 1; j < n; j++) {
      if (a[j] < a[minIdx]) minIdx = j;
    }
    if (minIdx !== i) [a[i], a[minIdx]] = [a[minIdx], a[i]];
  }
  return a;
}

/**
 * 插入排序：把当前元素插入到左侧已排序区的正确位置（像整理扑克牌）
 * 对「近乎有序」的数据是 O(n)，常数极小 -> TimSort 在小数组上就用它
 */
function insertionSort(arr) {
  const a = [...arr];
  const n = a.length;
  if (n <= 1) return a;

  for (let i = 1; i < n; i++) {
    const cur = a[i];
    let j = i - 1;
    // 严格大于才后移 -> 相等时停下、插在其后 -> 稳定
    while (j >= 0 && a[j] > cur) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = cur;
  }
  return a;
}

/**
 * 归并排序：分治，先递归排好两半，再线性合并
 * 稳定（merge 用 <=），时间恒定 O(n log n)，代价是 O(n) 辅助空间
 */
function mergeSort(arr) {
  if (!arr || arr.length <= 1) return arr ? [...arr] : [];

  const mid = arr.length >> 1;
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(left, right) {
  const res = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    // <= 保证稳定性：相等时优先取左半（原来在前面的）
    if (left[i] <= right[j]) res.push(left[i++]);
    else res.push(right[j++]);
  }
  // 剩余部分直接拼接
  while (i < left.length) res.push(left[i++]);
  while (j < right.length) res.push(right[j++]);
  return res;
}

// 自查（四个函数都应通过）
// f([])            -> []
// f([1])           -> [1]
// f([2,1])         -> [1,2]
// f([3,3,3])       -> [3,3,3]
// f([5,4,3,2,1])   -> [1,2,3,4,5]
// f([0,-1,2,-1])   -> [-1,-1,0,2]

/**
 * 模板 0：递归版标准二分（面试有时会点名要递归）
 */
function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
  if (!arr || arr.length === 0) return -1;
  if (left > right) return -1;                    // 递归出口：区间为空

  const mid = left + ((right - left) >> 1);       // 防溢出习惯写法
  if (arr[mid] === target) return mid;
  if (arr[mid] < target) return binarySearchRecursive(arr, target, mid + 1, right);
  return binarySearchRecursive(arr, target, left, mid - 1);
}

/**
 * 模板 1：非递归标准二分 —— 闭区间 [left, right]
 * 找到返回下标，找不到返回 -1
 */
function binarySearch(arr, target) {
  if (!arr || arr.length === 0) return -1;
  let left = 0;
  let right = arr.length - 1;                     // 闭区间：right 是可取的

  while (left <= right) {                         // 闭区间 -> 用 <=（left===right 时区间非空）
    const mid = left + ((right - left) >> 1);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;        // 目标在右侧，mid 已排除
    else right = mid - 1;                         // 目标在左侧，mid 已排除
  }
  return -1;
}

/**
 * 模板 2：左边界 lower_bound —— 第一个 >= target 的下标
 * 若所有元素都 < target，返回 arr.length（即插入位置）
 */
function lowerBound(arr, target) {
  if (!arr) return 0;
  let left = 0;
  let right = arr.length;                         // 注意是 length，搜索区间 [left, right)

  while (left < right) {
    const mid = left + ((right - left) >> 1);
    if (arr[mid] < target) left = mid + 1;        // mid 太小，排除
    else right = mid;                             // arr[mid] >= target，mid 可能就是答案，保留
  }
  return left;                                    // left === right，即答案位置
}

/**
 * 模板 3：右边界 upper_bound —— 第一个 > target 的下标
 */
function upperBound(arr, target) {
  if (!arr) return 0;
  let left = 0;
  let right = arr.length;

  while (left < right) {
    const mid = left + ((right - left) >> 1);
    if (arr[mid] <= target) left = mid + 1;       // 只差这里：<= 而不是 <
    else right = mid;
  }
  return left;
}

/** 应用：统计 target 出现次数 */
function countTarget(arr, target) {
  return upperBound(arr, target) - lowerBound(arr, target);
}

/** 应用：LC34 查找元素的第一个和最后一个位置 */
function searchRange(nums, target) {
  const lo = lowerBound(nums, target);
  // 没找到：lo 越界 或 该位置不是 target
  if (lo >= nums.length || nums[lo] !== target) return [-1, -1];
  return [lo, upperBound(nums, target) - 1];
}

// 自查
// binarySearch([], 1)              -> -1
// binarySearch([1], 1)             -> 0
// binarySearch([1], 2)             -> -1
// binarySearch([1,2,3,4,5], 5)     -> 4   （找末尾元素）
// lowerBound([1,2,2,2,3], 2)       -> 1
// upperBound([1,2,2,2,3], 2)       -> 4
// countTarget([1,2,2,2,3], 2)      -> 3
// lowerBound([1,2,3], 99)          -> 3   （全都小于 target，返回 length）
// lowerBound([1,2,3], 0)           -> 0   （全都大于 target）
// searchRange([5,7,7,8,8,10], 8)   -> [3,4]
// searchRange([5,7,7,8,8,10], 6)   -> [-1,-1]

/**
 * 字符串逆序 —— 三个版本，逐层递进
 */
// 版本 1：最短，但有 emoji 坑
function reverseStrNaive(str) {
  if (!str) return '';                       // 边界：null / undefined / ''
  return str.split('').reverse().join('');
}
// reverseStrNaive('abc')  -> 'cba'   ✓
// reverseStrNaive('a😀b') -> 'b\uDE00\uD83D a' ✗ emoji 被拆坏

// 版本 2：按码点，正确处理 emoji / 生僻字
function reverseStr(str) {
  if (!str) return '';
  return [...str].reverse().join('');        // 字符串迭代器按 code point 遍历
}
// reverseStr('a😀b') -> 'b😀a'  ✓

// 版本 3：按「字素簇」，连 ZWJ 组合 emoji 也正确（最严谨）
function reverseStrGrapheme(str) {
  if (!str) return '';
  if (typeof Intl === 'undefined' || !Intl.Segmenter) return reverseStr(str);
  const seg = new Intl.Segmenter('zh', { granularity: 'grapheme' });
  return [...seg.segment(str)].map(s => s.segment).reverse().join('');
}
// reverseStrGrapheme('a👨‍👩‍👧‍👦b') -> 'b👨‍👩‍👧‍👦a'  ✓

// 版本 4：手写循环（不用内置 API，面试官可能要求）
function reverseStrManual(str) {
  if (!str) return '';
  let res = '';
  for (let i = str.length - 1; i >= 0; i--) res += str[i];
  return res;
  // 注：JS 字符串不可变，+= 在 V8 里用 rope/ConsString 优化，实际不是 O(n^2)，
  //     但大量拼接仍建议用数组 push + join
}

/**
 * 判断回文 —— 双指针，O(1) 额外空间
 */
function isPalindrome(str) {
  if (str == null) return false;
  if (str.length <= 1) return true;          // 边界：'' 和单字符都是回文

  let left = 0;
  let right = str.length - 1;
  while (left < right) {
    if (str[left] !== str[right]) return false;   // 一旦不等立刻返回，无需走完
    left++;
    right--;
  }
  return true;
}

/**
 * LC125 验证回文串 —— 忽略大小写和非字母数字字符
 * 用双指针原地跳过，避免生成新字符串（比先 replace 再判断更省内存）
 */
function isPalindromeLoose(s) {
  if (s == null) return false;
  const isAlnum = c => /[a-z0-9]/i.test(c);

  let left = 0, right = s.length - 1;
  while (left < right) {
    while (left < right && !isAlnum(s[left])) left++;     // 左指针跳过非字母数字
    while (left < right && !isAlnum(s[right])) right--;   // 右指针同理
    if (left < right) {
      if (s[left].toLowerCase() !== s[right].toLowerCase()) return false;
      left++;
      right--;
    }
  }
  return true;
}

// 自查
// isPalindrome('')          -> true
// isPalindrome('a')         -> true
// isPalindrome('aa')        -> true
// isPalindrome('ab')        -> false
// isPalindrome('aba')       -> true
// isPalindromeLoose('A man, a plan, a canal: Panama') -> true
// isPalindromeLoose('race a car')                     -> false
// isPalindromeLoose(' ')                              -> true （全是非字母数字）

/** 迭代版：三指针，O(n) 时间 O(1) 空间 —— 面试首选 */
function reverseList(head) {
  let prev = null;
  let cur = head;
  while (cur) {
    const next = cur.next;   // 1. 先保存后继，防止断链后找不到
    cur.next = prev;         // 2. 反转指针方向
    prev = cur;              // 3. prev 右移
    cur = next;              // 4. cur 右移
  }
  return prev;               // cur 走到 null 时，prev 是新头
}

/** 递归版：O(n) 时间 O(n) 栈空间 */
function reverseListRecursive(head) {
  // 出口：空链表 或 只剩一个节点（它就是反转后的新头）
  if (!head || !head.next) return head;

  const newHead = reverseListRecursive(head.next);  // 先把后面全部反转好
  head.next.next = head;    // head.next 此刻是「已反转子链的尾节点」，把自己挂到它后面
  head.next = null;         // 断开旧的指向，否则 head 和 head.next 互指成环
  return newHead;           // 新头一路向上传递，不变
}

// 自查
// reverseList(null)     -> null
// reverseList([1])      -> [1]
// reverseList([1,2])    -> [2,1]
// reverseList([1,2,3])  -> [3,2,1]

/**
 * 返回链表倒数第 k 个节点，O(n) 一次遍历，O(1) 空间
 */
function getKthFromEnd(head, k) {
  if (!head || k <= 0) return null;          // 边界：空链表 / k 非法

  let fast = head;
  // fast 先走 k 步
  for (let i = 0; i < k; i++) {
    if (!fast) return null;                  // 边界：k 超过链表长度
    fast = fast.next;
  }

  let slow = head;
  while (fast) {                             // 同速前进，保持 k 的间距
    fast = fast.next;
    slow = slow.next;
  }
  return slow;
}

/** 变体 LC19：删除倒数第 n 个节点 —— 用 dummy 处理「删除头节点」的情况 */
function removeNthFromEnd(head, n) {
  const dummy = new ListNode(0, head);       // dummy 让「删头」和「删中间」逻辑统一
  let fast = dummy, slow = dummy;
  for (let i = 0; i <= n; i++) {             // 注意是 <=，让 slow 停在待删节点的「前驱」
    if (!fast) return head;
    fast = fast.next;
  }
  while (fast) { fast = fast.next; slow = slow.next; }
  slow.next = slow.next.next;                // 跳过待删节点
  return dummy.next;                         // 用 dummy.next 而不是 head（头可能被删了）
}

// 自查
// getKthFromEnd(null, 1)       -> null
// getKthFromEnd([1,2,3], 1)    -> 节点 3
// getKthFromEnd([1,2,3], 3)    -> 节点 1
// getKthFromEnd([1,2,3], 4)    -> null （k 超长）
// removeNthFromEnd([1], 1)     -> null （删掉唯一节点，验证 dummy 的必要性）

/** LC141 判断链表是否有环 */
function hasCycle(head) {
  if (!head || !head.next) return false;    // 边界：空链表 / 单节点无自环
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;         // 相遇 -> 有环
  }
  return false;                             // fast 到头 -> 无环
}

/** LC142 返回入环的第一个节点，无环返回 null */
function detectCycle(head) {
  if (!head || !head.next) return null;

  let slow = head, fast = head;
  // 阶段一：找相遇点
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      // 阶段二：一个回头，同速前进，相遇处即入环点
      // 依据 a = (k-1)·L + c
      let p = head;
      while (p !== slow) {
        p = p.next;
        slow = slow.next;
      }
      return p;
    }
  }
  return null;
}

// 自查
// hasCycle(null)                    -> false
// hasCycle([1])                     -> false
// hasCycle([1] 自环)                 -> true
// detectCycle([3,2,0,-4], pos=1)    -> 节点 2
// detectCycle([1,2], pos=0)         -> 节点 1
// detectCycle([1,2,3], 无环)         -> null

function mergeTwoLists(l1, l2) {
  if (!l1) return l2;                     // 边界：任一为空直接返回另一个
  if (!l2) return l1;

  const dummy = new ListNode(0);
  let tail = dummy;
  while (l1 && l2) {
    if (l1.val <= l2.val) { tail.next = l1; l1 = l1.next; }
    else                  { tail.next = l2; l2 = l2.next; }
    tail = tail.next;
  }
  tail.next = l1 || l2;                   // 剩余段整体接上，不用逐个搬
  return dummy.next;
}

/**
 * LC23 合并 K 个升序链表 —— 分治，O(N log k)
 */
function mergeKLists(lists) {
  if (!lists || lists.length === 0) return null;   // 边界：空数组
  return mergeRange(lists, 0, lists.length - 1);
}

function mergeRange(lists, lo, hi) {
  if (lo > hi) return null;
  if (lo === hi) return lists[lo];                 // 只剩一条，直接返回（可能是 null）

  const mid = lo + ((hi - lo) >> 1);
  const left = mergeRange(lists, lo, mid);
  const right = mergeRange(lists, mid + 1, hi);
  return mergeTwoLists(left, right);               // 复用 14.4
}

/**
 * 小顶堆版 —— 同样 O(N log k)，适合链表数极多 / 流式场景
 * 复用第 9 题的 MinHeap 思路，但比较的是节点的 val
 */
function mergeKListsByHeap(lists) {
  if (!lists || lists.length === 0) return null;

  // 简化实现：用数组模拟小顶堆（生产中应封装成通用堆）
  const heap = [];
  const push = (node) => {
    heap.push(node);
    let i = heap.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (heap[p].val <= heap[i].val) break;
      [heap[p], heap[i]] = [heap[i], heap[p]];
      i = p;
    }
  };
  const pop = () => {
    const top = heap[0];
    const last = heap.pop();
    if (heap.length) {
      heap[0] = last;
      let i = 0;
      while (true) {
        const l = 2 * i + 1, r = 2 * i + 2;
        let m = i;
        if (l < heap.length && heap[l].val < heap[m].val) m = l;
        if (r < heap.length && heap[r].val < heap[m].val) m = r;
        if (m === i) break;
        [heap[m], heap[i]] = [heap[i], heap[m]];
        i = m;
      }
    }
    return top;
  };

  for (const node of lists) if (node) push(node);  // 边界：跳过空链表

  const dummy = new ListNode(0);
  let tail = dummy;
  while (heap.length) {
    const node = pop();
    tail.next = node;
    tail = tail.next;
    if (node.next) push(node.next);               // 该链表的下一个节点补位
  }
  tail.next = null;                                // 断尾，防止残留旧指针
  return dummy.next;
}

// 自查
// mergeKLists([])                   -> null
// mergeKLists([null])               -> null      （链表数组里全是空链表）
// mergeKLists([null, [1], null])    -> [1]
// mergeKLists([[1,4,5],[1,3,4],[2,6]]) -> [1,1,2,3,4,4,5,6]

/* ============ 递归三序 ============ */
function preorderRecursive(root, res = []) {
  if (!root) return res;
  res.push(root.val);                    // 根
  preorderRecursive(root.left, res);     // 左
  preorderRecursive(root.right, res);    // 右
  return res;
}

function inorderRecursive(root, res = []) {
  if (!root) return res;
  inorderRecursive(root.left, res);
  res.push(root.val);                    // 根放中间
  inorderRecursive(root.right, res);
  return res;
}

function postorderRecursive(root, res = []) {
  if (!root) return res;
  postorderRecursive(root.left, res);
  postorderRecursive(root.right, res);
  res.push(root.val);                    // 根放最后
  return res;
}

/* ============ 非递归（栈）实现 ============ */

/** 前序非递归：栈，先压右后压左 */
function preorderIterative(root) {
  const res = [];
  if (!root) return res;                 // 边界：空树
  const stack = [root];
  while (stack.length) {
    const node = stack.pop();
    res.push(node.val);
    // 栈是 LIFO，想让左子树先被处理，就后压左
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }
  return res;
}

/** 中序非递归：cur 指针一路向左压栈，弹出访问后转右 */
function inorderIterative(root) {
  const res = [];
  const stack = [];
  let cur = root;
  while (cur || stack.length) {
    while (cur) {                        // 一路向左，把路径上的节点全压栈
      stack.push(cur);
      cur = cur.left;
    }
    cur = stack.pop();                   // 走到最左端，弹出访问
    res.push(cur.val);
    cur = cur.right;                     // 转向右子树，重复上述过程
  }
  return res;
}

/** 后序非递归（写法 1：根右左 + 反转）—— 面试首选，最不易错 */
function postorderIterative(root) {
  const res = [];
  if (!root) return res;
  const stack = [root];
  while (stack.length) {
    const node = stack.pop();
    res.push(node.val);
    // 注意：这里是先压左后压右 -> 出栈顺序 根、右、左
    if (node.left) stack.push(node.left);
    if (node.right) stack.push(node.right);
  }
  return res.reverse();                  // 反转「根右左」得到「左右根」
}

/** 后序非递归（写法 2：单栈 + lastVisited）—— 正统解法 */
function postorderIterativeStrict(root) {
  const res = [];
  const stack = [];
  let cur = root;
  let lastVisited = null;                // 记录上一个被访问（输出）的节点

  while (cur || stack.length) {
    while (cur) { stack.push(cur); cur = cur.left; }
    const peek = stack[stack.length - 1];
    // 右子树存在 且 还没被访问过 -> 先去右子树
    if (peek.right && lastVisited !== peek.right) {
      cur = peek.right;
    } else {
      res.push(peek.val);                // 左右都处理完了，可以访问根
      lastVisited = stack.pop();
    }
  }
  return res;
}

/* ============ 层序 BFS ============ */

/** LC102 层序遍历，返回二维数组（每层一个数组） */
function levelOrder(root) {
  const res = [];
  if (!root) return res;
  const queue = [root];
  while (queue.length) {
    const size = queue.length;           // 必须先固定当前层大小
    const level = [];
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    res.push(level);
  }
  return res;
}

/* ============ 深度 ============ */

/** LC104 最大深度 */
function maxDepth(root) {
  if (!root) return 0;                   // 边界：空树深度 0
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

/**
 * LC111 最小深度 —— 陷阱题！
 * 定义：根到「最近叶子节点」的距离。叶子 = 左右子树都为空。
 * 不能直接写 1 + min(left, right)：单支树时空的那一边会返回 0，答案就错了。
 */
function minDepth(root) {
  if (!root) return 0;
  // 关键：只有一个子树存在时，必须走那个存在的子树（另一边不是叶子路径）
  if (!root.left) return 1 + minDepth(root.right);
  if (!root.right) return 1 + minDepth(root.left);
  return 1 + Math.min(minDepth(root.left), minDepth(root.right));
}

/** 最小深度的 BFS 版本 —— 找到第一个叶子就返回，通常更快 */
function minDepthBFS(root) {
  if (!root) return 0;
  const queue = [root];
  let depth = 1;
  while (queue.length) {
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      if (!node.left && !node.right) return depth;   // 遇到第一个叶子，立即返回
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    depth++;
  }
  return depth;
}

/* ============ 路径总和 ============ */

/** LC112 路径总和 I：是否存在 根->叶 路径，其和等于 targetSum */
function hasPathSum(root, targetSum) {
  if (!root) return false;               // 边界：空树没有任何根到叶路径
  // 到达叶子节点：检查剩余值是否恰好被消耗完
  if (!root.left && !root.right) return targetSum === root.val;
  const rest = targetSum - root.val;
  return hasPathSum(root.left, rest) || hasPathSum(root.right, rest);
}

/** LC113 路径总和 II：返回所有满足条件的路径 */
function pathSum(root, targetSum) {
  const res = [];
  const path = [];

  const dfs = (node, remain) => {
    if (!node) return;
    path.push(node.val);
    remain -= node.val;

    if (!node.left && !node.right && remain === 0) {
      res.push([...path]);               // 必须拷贝
    } else {
      dfs(node.left, remain);
      dfs(node.right, remain);
    }
    path.pop();                          // 回溯：撤销选择
  };

  dfs(root, targetSum);
  return res;
}

// 自查
// preorderIterative(null)      -> []
// inorderIterative([1])        -> [1]
// levelOrder(null)             -> []
// maxDepth(null)               -> 0
// minDepth([1,2])              -> 2   （不是 1！左单支，验证陷阱）
// minDepth([1,null,2,null,3])  -> 3   （右斜链）
// hasPathSum(null, 0)          -> false （空树永远 false，即使 target 是 0）
// hasPathSum([1,2], 1)         -> false （1 不是叶子，不能中途结束）
// hasPathSum([-2,null,-3], -5) -> true  （含负数）
// pathSum([5,4,8,11,null,13,4,7,2,null,null,5,1], 22) -> [[5,4,11,2],[5,8,4,5]]