# 数据结构与算法

## 1. 链表

> **场景**：操作历史记录（浏览器前进后退）、LRU 缓存淘汰、撤销重做功能、音乐播放列表。
> **解决**：频繁插入/删除场景下数组性能差的问题，O(1) 插入删除。

### 反转链表

**是什么**：将链表中所有节点的指向反转，原来的尾节点变成头节点，原来的头节点变成尾节点。

**解决什么问题**：实现浏览器的后退功能、回文链表判断、链表相加时需要从低位开始等场景。

```js
function reverseList(head) {
  let prev = null, curr = head;  // prev 记录前一个节点
  while (curr) {
    const next = curr.next;  // 暂存下一个节点
    curr.next = prev;        // 将当前节点指向前一个（反转）
    prev = curr;             // prev 前移
    curr = next;             // curr 前移
  }
  return prev;  // prev 就是新的头节点
}
```

### 环形链表判断

**什么是环形链表？**
环形链表是指链表中某个节点的 `next` 指针指向了链表中之前的某个节点，从而形成一个闭环。遍历这种链表时会陷入无限循环，永远无法到达 `null`。

```
正常链表:  1 -> 2 -> 3 -> 4 -> null
环形链表:  1 -> 2 -> 3 -> 4
               ↑         ↓
               └─────────┘
```

**实际应用场景：**
- **内存泄漏检测**：对象间循环引用导致垃圾回收器无法回收，需要检测环
- **死锁检测**：进程等待资源形成环形依赖时会发生死锁
- **约瑟夫环问题**：n 个人围成一圈报数淘汰的经典算法问题
- **循环播放列表**：音乐/视频循环播放时最后一项指向第一项
- **游戏地图边界**：无缝世界地图从一端走到另一端

```js
// 快慢指针法：如果有环，快指针一定会追上慢指针
function hasCycle(head) {
  let slow = head, fast = head;  // 两指针都从头开始
  while (fast?.next) {           // fast 能继续走两步
    slow = slow.next;            // 慢指针走一步
    fast = fast.next.next;       // 快指针走两步
    if (slow === fast) return true;  // 相遇说明有环
  }
  return false;  // fast 走到结尾，无环
}
```

### 合并有序链表

**是什么**：将两个已排序的链表合并成一个新的有序链表。

**解决什么问题**：归并排序的核心操作、多个有序数据源的合并（如合并多个排行榜）、K路归并问题的基础。

```js
function mergeTwoLists(l1, l2) {
  const dummy = { next: null };  // 哑节点，简化处理
  let curr = dummy;
  while (l1 && 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 || l2;  // 接上剩余部分
  return dummy.next;     // 返回哑节点的下一个即真正头节点
}
```

---

## 2. 二叉树

> **场景**：DOM 树遍历、文件目录结构、组织架构图、表达式解析、前端路由匹配。
> **解决**：层级数据的存储与高效查找，遍历、搜索与路径问题。

### 遍历（前中后序）

**是什么**：按照特定顺序访问树中的每个节点。前序（根-左-右）、中序（左-根-右）、后序（左-右-根）。

**解决什么问题**：前序用于复制树结构、序列化；中序用于二叉搜索树获取有序数组；后序用于计算目录大小、删除节点。

```js
// 前序遍历：根 -> 左 -> 右（先访问根节点）
const preorder = (root, res = []) => {
  if (!root) return res;
  res.push(root.val);         // 访问根
  preorder(root.left, res);   // 递归左子树
  preorder(root.right, res);  // 递归右子树
  return res;
};

// 中序遍历：左 -> 根 -> 右（二叉搜索树得到有序数组）
const inorder = (root, res = []) => {
  if (!root) return res;
  inorder(root.left, res);    // 先左
  res.push(root.val);         // 再根
  inorder(root.right, res);   // 后右
  return res;
};

// 后序遍历：左 -> 右 -> 根（常用于删除操作）
const postorder = (root, res = []) => {
  if (!root) return res;
  postorder(root.left, res);  // 先左
  postorder(root.right, res); // 再右
  res.push(root.val);         // 最后根
  return res;
};
```

### 求最大深度

**是什么**：计算从根节点到最远叶子节点的最长路径上的节点数。

**解决什么问题**：判断 DOM 树嵌套层级是否过深、计算组织架构层级、平衡树检测的基础操作。

```js
// 递归求最大深度：左右子树深度的较大值 + 1
const maxDepth = root => {
  if (!root) return 0;  // 空节点深度为 0
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
};
```

### 路径和

**是什么**：判断树中是否存在一条从根到叶子的路径，使得路径上所有节点值之和等于目标值。

**解决什么问题**：决策树路径分析、文件系统权限累加判断、游戏技能树点数计算。

```js
// 判断是否存在根到叶子的路径，使得路径上所有节点值之和等于目标值
function hasPathSum(root, targetSum) {
  if (!root) return false;
  // 叶子节点：检查剩余值是否等于当前节点值
  if (!root.left && !root.right) return targetSum === root.val;
  // 递归检查左右子树，目标值减去当前节点值
  return hasPathSum(root.left, targetSum - root.val) 
      || hasPathSum(root.right, targetSum - root.val);
}
```

---

## 3. 栈与队列

> **场景**：栈用于括号匹配、撤销操作、函数调用栈；队列用于任务调度、消息队列、BFS 广度优先搜索。
> **解决**：先进后出/先进先出的数据操作顺序控制。

### 用栈实现队列

**是什么**：使用两个栈（后进先出）来模拟队列（先进先出）的行为。

**解决什么问题**：理解数据结构转换思想、在只支持栈操作的环境中实现队列、面试高频考点。

```js
// 使用两个栈实现队列：入栈和出栈
class MyQueue {
  constructor() {
    this.inStack = [];   // 入队栈
    this.outStack = [];  // 出队栈
  }
  
  // 入队：直接压入 inStack
  push(x) { this.inStack.push(x); }
  
  // 出队：从 outStack 取，如果空则把 inStack 全部倒入 outStack
  pop() {
    if (!this.outStack.length) {
      while (this.inStack.length) this.outStack.push(this.inStack.pop());
    }
    return this.outStack.pop();
  }
  
  // 查看队首：同 pop 逻辑，但不弹出
  peek() {
    if (!this.outStack.length) {
      while (this.inStack.length) this.outStack.push(this.inStack.pop());
    }
    return this.outStack[this.outStack.length - 1];
  }
  
  // 判断是否为空
  empty() { return !this.inStack.length && !this.outStack.length; }
}
```

### 有效的括号

**是什么**：判断一个只包含括号的字符串中，所有括号是否正确配对和嵌套。

**解决什么问题**：代码编辑器语法检查、表达式合法性验证、HTML/XML 标签配对检测。

```js
function isValid(s) {
  // 右括号到左括号的映射
  const map = { ')': '(', ']': '[', '}': '{' };
  const stack = [];
  for (const c of s) {
    if (map[c]) {  // 如果是右括号
      // 栈顶必须是对应的左括号
      if (stack.pop() !== map[c]) return false;
    } else {
      stack.push(c);  // 左括号入栈
    }
  }
  return !stack.length;  // 栈必须为空才有效
}
```

---

## 4. 哈希表

> **场景**：快速查找（用户ID查询）、统计词频、数据去重、分组操作。
> **解决**：O(1) 时间复杂度的键值对存储和查找，避免线性遍历。

### 两数之和

**是什么**：在数组中找到两个数，使它们的和等于目标值，返回这两个数的索引。

**解决什么问题**：配对查找问题的基础模型、购物车凑单、找零钱问题的简化版。

```js
// 用哈希表存储已遍历的数字及其索引
function twoSum(nums, target) {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const diff = target - nums[i];  // 计算需要的配对数字
    if (map.has(diff)) return [map.get(diff), i];  // 找到则返回两个索引
    map.set(nums[i], i);  // 存储当前数字和索引
  }
  return [];
}
```

### 字母异位词分组

**是什么**：将字母相同但顺序不同的单词归为一组（如 "eat" 和 "tea"）。

**解决什么问题**：搜索引擎同义词处理、单词游戏（如 Wordle 变体）、文本相似度分析。

```js
// 异位词排序后结果相同，以此为 key 分组
function groupAnagrams(strs) {
  const map = new Map();
  for (const s of strs) {
    const key = [...s].sort().join('');  // 排序后作为 key
    map.set(key, (map.get(key) || []).concat(s));  // 加入对应分组
  }
  return [...map.values()];  // 返回所有分组
}
```

---

## 5. 排序算法

> **场景**：商品价格/销量排序、排行榜、数据可视化预处理。
> **解决**：无序数据有序化，理解分治思想（快排、归并）是算法基础。

### 快速排序

**是什么**：选取一个基准值，将数组分成小于和大于基准值的两部分，递归排序。平均 O(n log n)。

**解决什么问题**：通用排序场景、理解分治思想、Top K 问题可用快速选择优化。

```js
// 快速排序：分治思想，选取基准值分区
function quickSort(arr) {
  if (arr.length <= 1) return arr;  // 基准情况
  const pivot = arr[Math.floor(arr.length / 2)];  // 选取中间元素为基准值
  const left = arr.filter(x => x < pivot);    // 小于基准值
  const middle = arr.filter(x => x === pivot); // 等于基准值
  const right = arr.filter(x => x > pivot);   // 大于基准值
  // 递归排序左右部分，合并结果
  return [...quickSort(left), ...middle, ...quickSort(right)];
}
```

### 归并排序

**是什么**：将数组不断二分到单个元素，再两两合并成有序数组。稳定排序，O(n log n)。

**解决什么问题**：需要稳定排序的场景、外部排序（大文件排序）、求逆序对数量。

```js
// 归并排序：分治思想，先拆分再合并
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));   // 递归排序左半部分
  const right = mergeSort(arr.slice(mid));     // 递归排序右半部分
  return merge(left, right);  // 合并两个有序数组
}

// 合并两个有序数组
function merge(left, right) {
  const result = [];
  let i = 0, j = 0;
  // 双指针比较，取较小的元素
  while (i < left.length && j < right.length) {
    result.push(left[i] < right[j] ? left[i++] : right[j++]);
  }
  // 拼接剩余部分
  return result.concat(left.slice(i), right.slice(j));
}
```

---

## 6. 二分查找

> **场景**：有序列表快速定位（分页跳转）、版本号查找、IP 地址归属地查询、猜数字游戏。
> **解决**：在有序数据中 O(log n) 时间复杂度快速查找，比线性查找效率高很多。

### 基础二分查找

**是什么**：在有序数组中，每次比较中间元素，将搜索范围缩小一半。O(log n) 时间复杂度。

**解决什么问题**：有序数据快速定位、Git bisect 查找 bug 引入版本、分页跳转到指定页。

```js
// 标准二分查找：在有序数组中查找目标值
function binarySearch(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);  // 计算中间位置
    if (arr[mid] === target) return mid;  // 找到目标
    // 根据大小关系缩小范围
    arr[mid] < target ? (left = mid + 1) : (right = mid - 1);
  }
  return -1;  // 未找到
}
```

### 旋转数组查找

**是什么**：在一个被旋转过的有序数组（如 [4,5,6,7,0,1,2]）中查找目标值。

**解决什么问题**：日志轮转后的时间查找、循环数组中的搜索、二分查找的变体考察。

```js
// 旋转数组查找：数组被旋转过，如 [4,5,6,7,0,1,2]
function searchRotated(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) return mid;
    
    // 判断哪一半是有序的
    if (nums[left] <= nums[mid]) {  // 左半边有序
      // target 在左半边有序区间内
      if (target >= nums[left] && target < nums[mid]) right = mid - 1;
      else left = mid + 1;
    } else {  // 右半边有序
      // target 在右半边有序区间内
      if (target > nums[mid] && target <= nums[right]) left = mid + 1;
      else right = mid - 1;
    }
  }
  return -1;
}
```

---

## 7. 斐波那契数列

> **场景**：算法入门经典题、理解递归与动态规划思想、缓存优化演示、爬楼梯问题变种。
> **解决**：求第 n 位斐波那契数（F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)）。

### 方法一：普通递归（不推荐）

```js
// 时间复杂度 O(2^n)，存在大量重复计算
function fib(n) {
  if (n <= 1) return n;  // 基准情况：F(0)=0, F(1)=1
  return fib(n - 1) + fib(n - 2);  // 递归调用
}
```

### 方法二：记忆化递归

```js
// 时间复杂度 O(n)，空间复杂度 O(n)
function fib(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];  // 已计算过，直接返回缓存
  return memo[n] = fib(n - 1, memo) + fib(n - 2, memo);  // 计算并缓存
}
```

### 方法三：动态规划

```js
// 时间复杂度 O(n)，空间复杂度 O(n)
function fib(n) {
  if (n <= 1) return n;
  const dp = [0, 1];  // dp[i] 表示第 i 位斐波那契数
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];  // 状态转移方程
  }
  return dp[n];
}
```

### 方法四：空间优化（推荐）

```js
// 时间复杂度 O(n)，空间复杂度 O(1)
function fib(n) {
  if (n <= 1) return n;
  let prev = 0, curr = 1;  // 只保留前两个值
  for (let i = 2; i <= n; i++) {
    [prev, curr] = [curr, prev + curr];  // 滚动更新
  }
  return curr;
}
```

### 方法五：矩阵快速幂（大数优化）

```js
// 时间复杂度 O(log n)，适合求极大位数
// 原理：|F(n)  |   |1 1|^(n-1)   |F(1)|
//       |F(n-1)| = |1 0|       * |F(0)|
function fib(n) {
  if (n <= 1) return n;
  
  // 2x2 矩阵乘法
  const multiply = (a, b) => [
    [a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]],
    [a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]]
  ];
  
  // 快速幂：计算 m^p
  const power = (m, p) => {
    let result = [[1, 0], [0, 1]]; // 单位矩阵
    while (p > 0) {
      if (p & 1) result = multiply(result, m);  // 奇数幂则乘一次
      m = multiply(m, m);  // 底数平方
      p >>= 1;             // 指数减半
    }
    return result;
  };
  
  const matrix = [[1, 1], [1, 0]];
  return power(matrix, n - 1)[0][0];  // 结果在左上角
}
```

| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|------|-----------|-----------|----------|
| 普通递归 | O(2^n) | O(n) | 仅理解思想 |
| 记忆化递归 | O(n) | O(n) | 面试常考 |
| 动态规划 | O(n) | O(n) | 面试常考 |
| 空间优化 | O(n) | O(1) | **推荐** |
| 矩阵快速幂 | O(log n) | O(1) | 大数/竞赛 |