链表在面试中常考操作包括：

• 指针操作：反转链表（LeetCode 206）、合并两个有序链表（21）
• 快慢指针：找中点、判断环、找环入口
• 虚拟头节点：简化边界处理（如删除头节点）

【经典例题】链表中环的入口节点（LeetCode 142）

题目：给一个链表，返回链表开始入环的第一个节点。若无环则返回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) {
      // 有环，找入口
      slow = head;
      while (slow !== fast) {
        slow = slow.next;
        fast = fast.next;
      }
      return slow;
    }
  }
  return null;
}

面试高频变式：

• 合并K个有序链表（优先队列/分治）
• 重排链表（L→L1→L2→…→Ln → L→Ln→L1→Ln-1→…）
• 两数相加（链表逆序存储数字）

哈希表（Hash Table）是实现O(1)时间复杂度查找的关键结构，面试重点包括：

• 哈希冲突处理：开放地址法、链地址法
• 哈希函数设计：字符串哈希（进制转换）、大整数取模
• 实际应用：两数之和、最长无重复子串、LRU缓存

【经典例题】两数之和（LeetCode 1）

function twoSum(nums, target) {
  const map = new Map(); // 值 → 索引
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (map.has(complement)) {
      return [map.get(complement), i];
    }
    map.set(nums[i], i);
  }
  return [];
}
// 示例
console.log(twoSum([2,7,11,15], 9)); // [0,1]

注意：JS中Map比Object更适合存储键值对（避免原型污染），且保持插入顺序。

队列（Queue）遵循先进先出（FIFO）原则，关键应用：

• BFS算法：层序遍历、最短路径
• 缓冲区设计：生产者-消费者模型
• 双端队列：滑动窗口最大值、构建最大子序列

【经典例题】二叉树层序遍历（LeetCode 102）

function levelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];
  while (queue.length > 0) {
    const levelSize = queue.length;
    const level = [];
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

双端队列变式：用双端队列实现滑动窗口最大值（LeetCode 239），时间复杂度O(n)。

单调结构（Monotonic Structure）通过维护栈/队列的单调性，实现高效查询：

• 单调栈：求“下一个更大元素”、“柱状图最大矩形”
• 单调队列：滑动窗口最值（O(n)时间）

【经典例题】下一个更大元素 I（LeetCode 496）

function nextGreaterElement(nums1, nums2) {
  const map = new Map();
  const stack = [];
  // 遍历nums2，构建映射
  for (let num of nums2) {
    while (stack.length > 0 && stack[stack.length - 1] < num) {
      map.set(stack.pop(), num);
    }
    stack.push(num);
  }
  // 处理无更大元素的情况
  while (stack.length > 0) {
    map.set(stack.pop(), -1);
  }
  // 生成结果
  return nums1.map(num => map.get(num));
}
// 测试
console.log(nextGreaterElement([4,1,2], [1,3,4,2])); // [-1,3,-1]

关键点：栈中保持递减，当新元素更大时，弹出所有更小元素并记录映射。

BST性质：左子树所有节点 < 根节点 < 右子树所有节点；中序遍历有序。

核心操作：

• 查找：O(log n)（平衡时）→ O(n)（退化为链表）
• 插入：按BST性质递归/迭代插入
• 删除：分三种情况（无子/单子/双子）

【经典例题】二叉搜索树中第K小的元素（LeetCode 230）

function kthSmallest(root, k) {
  let count = 0;
  let result = -1;
  function inorder(node) {
    if (!node || result !== -1) return;
    inorder(node.left);
    count++;
    if (count === k) {
      result = node.val;
      return;
    }
    inorder(node.right);
  }
  inorder(root);
  return result;
}

进阶优化：在节点中存储子树大小，实现O(log n)时间查找第K小。

平衡树：任意节点左右子树高度差≤1（如AVL树、红黑树）。

红黑树五大性质：

1. 节点是红或黑
2. 根节点是黑
3. 叶子节点（NULL）是黑
4. 红节点的子节点是黑
5. 任一节点到其叶子节点的所有路径含相同黑节点数

【实际应用】：Java HashMap（1.8+）、Linux进程调度（CFS）、数据库索引。

【面试高频问题】为什么HashMap用红黑树不用AVL？

答：红黑树牺牲部分平衡性（允许高度差2），但旋转次数更少，插入/删除效率更高。HashMap中节点数≤8时用链表，＞8且容量≥64时转红黑树，平衡性要求适中。

Dijkstra算法：求单源最短路径（非负权图），时间O((V+E)log V)。

Floyd-Warshall：多源最短路径，O(V³)，适合小规模图。

Bellman-Ford：支持负权边，检测负环。

【经典例题】网络延迟时间（LeetCode 743）

function networkDelayTime(times, n, k) {
  // 构建邻接表
  const graph = Array.from({ length: n + 1 }, () => []);
  for (const [u, v, w] of times) {
    graph[u].push([v, w]);
  }
  // 初始化距离数组
  const dist = new Array(n + 1).fill(Infinity);
  dist[k] = 0;
  // 优先队列：[距离, 节点]
  const pq = [[0, k]];
  while (pq.length > 0) {
    // 取最小距离节点
    pq.sort((a, b) => a[0] - b[0]);
    const [d, node] = pq.shift();
    // 已访问过更短路径则跳过
    if (d > dist[node]) continue;
    // 更新邻居
    for (const [neighbor, weight] of graph[node]) {
      const newDist = dist[node] + weight;
      if (newDist < dist[neighbor]) {
        dist[neighbor] = newDist;
        pq.push([newDist, neighbor]);
      }
    }
  }
  const maxDist = Math.max(...dist.slice(1));
  return maxDist === Infinity ? -1 : maxDist;
}

面试高频变式：带约束的最短路径（如最多转机K次）、最小生成树（Prim/Kruskal）。

拓扑排序：仅适用于有向无环图（DAG），常用于任务调度、依赖解析。

Kahn算法：基于入度的BFS；DFS法：后序遍历的逆序。

【典型应用】：课程安排、构建顺序、编译依赖。

【扩展知识】关键路径（Critical Path）：

• AOE网（Activity On Edge）：边表示活动，点表示事件
• 关键路径：从源点到汇点的最长路径
• 关键活动：最早开始时间=最晚开始时间的活动

实际场景：项目管理（PERT）、流水线调度。

标准二分：有序数组查找目标值。

变形场景：

• 旋转数组：[4,5,6,7,0,1,2]中找0
• 重复元素：找第一个/最后一个位置
• 二维矩阵：[1,3,5,7],[10,11,16,20],[23,30,34,60]中查找

【经典例题】在排序数组中查找元素的第一个和最后一个位置（LeetCode 34）

function searchRange(nums, target) {
  function findBound(isFirst) {
    let left = 0, right = nums.length - 1;
    while (left <= right) {
      const mid = left + Math.floor((right - left) / 2);
      if (nums[mid] > target || (isFirst && nums[mid] === target)) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
  const start = findBound(true);
  const end = findBound(false) - 1;
  return (start <= end && nums[start] === target)
    ? [start, end]
    : [-1, -1];
}

关键点：通过调整条件控制向左/右边界收缩。

四种解法对比：

【经典例题】数组中的第K个最大元素（LeetCode 215）

function findKthLargest(nums, k) {
  k = nums.length - k; // 转为第k小
  function quickSelect(left, right) {
    const pivotIndex = partition(left, right);
    if (pivotIndex === k) return nums[pivotIndex];
    if (pivotIndex > k) return quickSelect(left, pivotIndex - 1);
    return quickSelect(pivotIndex + 1, right);
  }
  function partition(left, right) {
    const pivot = nums[right];
    let i = left;
    for (let j = left; j < right; j++) {
      if (nums[j] <= pivot) {
        [nums[i], nums[j]] = [nums[j], nums[i]];
        i++;
      }
    }
    [nums[i], nums[right]] = [nums[right], nums[i]];
    return i;
  }
  return quickSelect(0, nums.length - 1);
}

堆解法：维护大小为k的小顶堆，堆顶即第K大。

贪心选择性质：局部最优可导致全局最优。

证明方法：数学归纳法、交换论证。

【经典例题】跳跃游戏（LeetCode 55）

function canJump(nums) {
  let maxReach = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > maxReach) return false;
    maxReach = Math.max(maxReach, i + nums[i]);
    if (maxReach >= nums.length - 1) return true;
  }
  return false;
}

反例：零钱兑换（不满足贪心）：[1,3,4]找6元，贪心→4+1+1（3枚），最优→3+3（2枚）。

回溯框架：

function backtrack(path, choices) {
  if (结束条件) {
    记录结果;
    return;
  }
  for (选择 in 可选选择) {
    做选择;
    backtrack(path, 新选择);
    撤销选择;
  }
}

【经典例题】全排列（LeetCode 46）

function permute(nums) {
  const result = [];
  function backtrack(path) {
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (path.includes(nums[i])) continue;
      path.push(nums[i]);
      backtrack(path);
      path.pop();
    }
  }
  backtrack([]);
  return result;
}

剪枝技巧：N皇后问题中检查列、主对角线、副对角线是否冲突。