哈希

查询流程：哈希→定位→桶内查找，三步均为常数开销，整体平均 $O(1)$。

• 哈希函数：$O(1)$ 计算键的哈希值，并对表长取模定位桶下标。
• 桶（Bucket）：直接用数组下标访问，定位到对应桶。
• 冲突解决：拉链法或开放地址法，保证每个桶平均元素数为常数级。

1. 两数之和

最直观的做法是两层嵌套循环 $O(n^2)$，每次都要去剩下的所有元素里找一个搭档，最坏得做 $\frac{n(n-1)}{2}$ 次检查。

要把暴力枚举的 $O(n^2)$ 降到 $O(n)$，关键就在于：能否用空间换时间，快速判断某个“补数”在不在已经遍历过的元素里？

1. 抽象核心：把「找两个数和为目标」的问题，转化为「对于每个 x，快速判断 target - x 有没有出现过」。
2. 数据结构选型：哈希表（unordered_map/HashMap）能在 $O(1)$ 内完成查找和插入。
3. 空间换时间：用额外 $O(n)$ 空间，换来一次遍历就能搞定，总体 $O(n)$ 时间。

class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:# 先查后存hashmap = {}for i, num in enumerate(nums):value = target - numif value in hashmap:return [i, hashmap[value]]hashmap[num] = ireturn []

Step 1. 用「哈希表」记录已遍历元素

• 当遍历到 x 时，想要的 y 必须满足 $y=\mathrm{target}-x$。
• 如果之前遇到过这样的 y，就能立即得到答案；如果还没遇到，就把当前的 x（和它的下标 i）记下来，以备后续查找。

Step 2. 思考「一遍完成」

• 一边遍历一边查，一遍遍历一遍插入，都是 $O(1)$ 的哈希操作。
• 总共只需要一次遍历，时间复杂度 $O(n)$，空间复杂度 $O(n)$。

这样的思考套路在很多「两数/多数之和」「前缀和＋查表」类型问题中都很常见：先想想能否把「全局搜索」的问题，转换成「边遍历边维护、查表」的形式，能的时候就能从 $O(n^2)$ 降到 $O(n)$，甚至更快。

用哈希的一遍扫描，是 Two Sum 的经典 $O(n)$ 解。理解了「先查后存」的思路，遇到类似的「和／差／积／距离」匹配问题，就能举一反三了。

49. 字母异位词分组

核心思路——找出能唯一表示“字母异位词组”的不变式。

1. 什么叫“字母异位词”？

   • 两个字符串各字母及出现次数一模一样，只是顺序不同。

2. 如何判断两串字母相同？

   • 把它们都“归一化”为同一个形式——这个形式要 可哈希（可以当做 dict 的 key）。

3. 常见的“归一化”手段：

   • 排序后的字符串：key = ''.join(sorted(s))
   • 字母计数元组：构造 26 长度的计数元组 key = tuple(counts)，其中 counts[i] 表示字母 chr(ord('a')+i) 在字符串里出现的次数。

这样就能 在一次遍历中把所有异位词分到同一个组里，时间复杂度 $O(NK\log K)$（排序）或 $O(NK)$（计数），其中 $N$ 是字符串数量，$K$ 是字符串最大长度。

class Solution:def groupAnagrams(self, strs: List[str]) -> List[List[str]]:hashmap = {}for str in strs:sorted_str = ''.join(sorted(str))  # 把变化的 str 转成固定的 str 作为 keyif sorted_str in hashmap:hashmap[sorted_str].append(str)else:hashmap[sorted_str] = [str]result = []for l in hashmap:result.append(hashmap[l])return result

当然可以使用高级一点的数据结构，defaultdict，

from collections import defaultdictdef group_anagrams(strs: List[str]) -> List[List[str]]:groups = defaultdict(list)  # key: 排序后字符串 -> 值：原始字符串列表for s in strs:key = ''.join(sorted(s))  # 将 s 中字符排序后拼成新串groups[key].append(s)return list(groups.values())  # 返回所有分组的列表

# print(sorted(s))                # ['a', 'e', 't'] ['a', 'e', 't'] ['a', 'n', 't'] 
sorted_str = ''.join(sorted(s))   # aet              aet             ant

128. 最长连续序列

题目：未排序数组，想找“值”上连续的最长片段。

• 问自己：怎样能 $O(1)$ 判断某个值在不在数组里？ → 选对数据结构：哈希集合，用 set 把它变成 $O(1)$，num_set = set(nums)，去重同时支持快速查找。
• 再想：如果对每个数都盲目向两边扩，会不会重复扫？→ 避免冗余扫描：只在真正的“起点”触发扩展，让每个元素在扩展里只被访问一次。遍历集合中的每个元素 x，只在“段首”（x-1 不存在）或“段尾”（x+1 不存在）开始扩，能保证每个数只被“扩展”访问一次。

def longest_consecutive(nums: List[int]) -> int:num_set = set(nums)  # 把所有数放进集合，去重并支持 O(1) 查询longest = 0for x in num_set:if x-1 not in num_set:  # 只有 x 是一个序列的「起点」时才去扩展length = 1while x + length in num_set:  # 向右不断扩展length += 1longest = max(longest, length)return longest

掌握这个套路，遇到“基于数值关系”的“最长、最短、计数”类问题，都可以先问：“我能不能用哈希把查找降到 $O(1)$？然后怎样只扫描一遍？”

双指针

用两根指针：一个遍历（快指针），一个定位目标位置（慢指针）。

283. 移动零

要在 原地、一次遍历 完成「把 0 都挪到末尾，同时保持其它元素相对顺序」的操作，思考的核心是：「有没有办法在一次遍历里，把非零元素“收拢”到数组前面，然后最后把剩下的位置都填 0？」

• 慢指针 last = 0：指向下一个应该放「非零元素」的位置。
• 快指针 i：遍历整个数组，遇到非零就往前复制／交换。

具体做法有两种变体：

• 变体 A：覆盖＋填零，

  • 第一遍，用快指针 i 从头到尾走：

    if nums[i] != 0:nums[last] = nums[i]last += 1
    

    这样，所有非零元素都会被依次写到 nums[0..last-1]。
  • 第二遍，把 nums[last..end] 全部置 0。

  这两次遍历仍然是 $O(n)$，而且只用了常数额外空间。

• 变体 B：原地交换

  1. 用快指针 i 从头到尾走：

     • 如果 nums[i] != 0，就和 nums[last] 交换，然后 last += 1。
     • 这样一来，非零都会被“冒泡”到前面，零慢慢被推到后面。

  2. 遍历一次结束，所有零都在 last 之后了。

  这也是一次遍历、常数空间的完美解。

def move_zeroes(nums: List[int]) -> None:last = 0  # 慢指针，目标位置，即下一个非零元素应该放到的位置for i in range(len(nums)):  # 快指针，用于遍历if nums[i] != 0:nums[last], nums[i] = nums[i], nums[last]  # 交换 nums[i] 和 nums[last]last += 1# 此时 [0..last-1] 都是原始的非零， [last..end] 全是 0

掌握「双指针收拢／交换」的思维，以后遇到「移除/重排」类的原地操作，都能快速想到类似套路。

11. 盛最多水的容器

要想出 $O(n)$ 的双指针解法，关键在于把「暴力枚举所有 $(i,j)$ 对」升级为「一次扫描，同时智能地跳过不可能更优的情况」。

1. 先从暴力法出发

   • 暴力地枚举所有 $i<j$，计算面积 $(j-i)\times \min (h[i],h[j])$，复杂度 $O(n^2)$，在 $n$ 达到 $10^5$ 级别时显然不可行。

2. 分析面积构成：面积 = 宽度 × 高度限制

   • 宽度由指针位置差决定：$\Delta x=j-i$。
   • 高度受两条线中 矮者 限制：$\min (h[i],h[j])$。

3. 提出双指针思路

   • 用两个指针 $l=0$、$r=n-1$ 从最宽处开始，中间装的水至少是当前最长宽度下能装的最大值。
   • 然后向内收窄宽度，想要弥补宽度减小带来的损失，只有办法是提高“矮边”的高度。

4. 为什么总是贪心移动“矮边”指针？

   • 假设当前 $h[l]<h[r]$：面积受限于 $h[l]$。
   • 如果我们只把 $r$ 向左移一格，宽度减小 1，新的高度上限 $\min (h[l],h[r-1])\le h[l]$，那么新面积 $\le (r-1-l)\times h[l]$，一定不比当前 $(r-l)\times h[l]$ 大。
   • 唯一可能获得“更高限高”的，是移动那条矮的那边（$l$ 向右），去找一个可能更高的 $h[l^{\prime }]$。

class Solution:def maxArea(self, height: List[int]) -> int:left, right = 0, len(height) - 1  # 双指针max_area = 0  # 记录最大容量while left < right:area = min(height[left], height[right]) * (right - left)  # 计算储存水量max_area = max(max_area, area)if height[left] < height[right]:  # 移动较短的left += 1else:right -= 1return max_area

这种「双指针＋贪心跳过不必要情况」的套路，遇到类似“面积/距离”之类的最值问题，也可以举一反三。

15. 三数之和

1. 排序：先对数组 nums 排序，方便双指针及去重。

2. 固定第一个数：遍历索引 i，跳过与前一个相同的数，避免重复三元组。

3. 双指针找两数：在区间 [i+1, n-1] 上用左右指针 l, r，计算 s = nums[l] + nums[r]：

   • s + nums[i] == 0 → 找到一组，记录并同时跳过 l/r 上的重复值；
   • s + nums[i] < 0 → l += 1；
   • s + nums[i] > 0 → r -= 1。

4. 时间复杂度：排序 $O(n\log n)$ + 双循环 $O(n^2)$。

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:nums.sort()n = len(nums)res = []for i in range(n-2):if i > 0 and nums[i] == nums[i-1]:  # 保证第一个数不重复continuetwo_sum = 0 - nums[i]left, right = i+1, n-1while(left < right):s = nums[left] + nums[right]if s == two_sum:res.append([nums[i], nums[left], nums[right]])while left < right and nums[left] == nums[left+1]:   # 保证第二个数不重复left += 1while left < right and nums[right] == nums[right-1]: # 保证第三个数不重复right -= 1left += 1right -= 1elif s < two_sum:left += 1elif s > two_sum:right -= 1return res

42. 接雨水

1. 暴力思路

   • 对于每个柱子 i，算出它左边最高的柱子 L = max(height[0..i])，右边最高的柱子 R = max(height[i..n‑1])。
   • 它能接的水就是 min(L, R) - height[i]（如果为负就当 0）。
   • 直接每次都去左右扫描找最大值，是两次 $O(n)$ 内循环，总 $O(n^2)$。

2. 去重计算：预处理左右最大

   • 既然 要多次用到「左侧最高」「右侧最高」，可以分别用两个数组事先算好：

     left_max[i]  = max(height[0..i])
     right_max[i] = max(height[i..n-1])
     

   • 这样每个位置只需 $O(1)$ 时间取 min(left_max[i], right_max[i]) - height[i]，整体 $O(n)$。

3. 进一步优化空间：双指针+即时维护最高

   • 注意到计算水量时，只关心当前 i 位置两侧的最高值，并且可以由「向内收缩」的过程中在线更新。

   • 维护两个指针 l=0, r=n‑1，以及对应的 maxL, maxR：

     • 当 height[l] < height[r]，说明左边高度更矮，当前 l 位上的水量只跟 maxL 有关，且不会被右边更高的边界限制：

       maxL = max(maxL, height[l])
       water += maxL - height[l]
       l += 1
       

     • 否则对称地处理右侧：

       maxR = max(maxR, height[r])
       water += maxR - height[r]
       r -= 1
       

   • 每步只走一个指针，更新一次水量，整体 $O(n)$、额外 $O(1)$ 空间。

def trap(height: List[int]) -> int:l, r = 0, len(height) - 1maxL = maxR = water = 0while l < r:if height[l] < height[r]:maxL = max(maxL, height[l])water += maxL - height[l]l += 1else:maxR = max(maxR, height[r])water += maxR - height[r]r -= 1return water

滑动窗口

3. 无重复字符的最长子串

滑动窗口＋哈希：在一次线性遍历里，维护一个「无重复字符的子串窗口」，实时更新它能达到的最大长度。

• 窗口定义：用左右指针 left、right 表示当前考察的子串 s[left…right]，保证其中无重复字符。

• 遇到重复：用字典 last 记录每个字符上次出现的位置。当 s[right] 在窗口内已有出现（last[s[right]] ≥ left）时，就把左指针 left 跳过那次出现的位置：

  left = max(left, last[s[right]] + 1)
  

  这样窗口重新变为无重复。

• 更新状态：每轮循环都做：

  • last[s[right]] = right （更新字符最新位置）
  • ans = max(ans, right - left + 1)（更新最大长度）

def length_of_longest_substring(s: str) -> int:last = {}      # 记录字符上次出现的索引left = 0       # 窗口左边界ans = 0for right, c in enumerate(s):if c in last and last[c] >= left:left = last[c] + 1  # 碰到重复，移动左界到上次出现位置的下一位last[c] = rightans = max(ans, right - left + 1)return ans

438. 找到字符串中所有字母异位词

滑动窗口＋计数对比：

• 固定窗口长度：因为异位词子串长度必定等于 |p|，我们就 只需在 s 上滑动一个恒定长度为 m = len(p) 的窗口，检查每个窗口里的字符多重集是否与 p 相同。

• 如何快速判断多重集相同？

  • 最直接的方法是对每个窗口都维护一个长度 26（字母集大小）的“计数数组” cnt_s，用于记录窗口内每个字母出现次数；同时为 p 事先计算好 cnt_p。
  • 当窗口滑动时，只需 减去出窗字符的计数、加上新进字符的计数，就能在 $O(1)$ 时间内更新 cnt_s。
  • 然后只要比较 cnt_s 与 cnt_p 是否相等，就可判定当前窗口是否为异位词。

def find_anagrams(s: str, p: str) -> List[int]:n, m = len(s), len(p)if n < m:return []# 构造长度为 26 的计数数组def make_count(arr_str: str) -> List[int]:cnt = [0] * 26base = ord('a')for ch in arr_str:cnt[ord(ch) - base] += 1return cntcnt_p = make_count(p)cnt_s = make_count(s[:m])ans = []if cnt_s == cnt_p:ans.append(0)base = ord('a')# 滑动窗口for i in range(m, n):cnt_s[ord(s[i-m]) - base] -= 1  # 出窗字符cnt_s[ord(s[i])   - base] += 1  # 新进字符if cnt_s == cnt_p:ans.append(i - m + 1)return ans

借助“先初始化一次、后续只做局部增删”的思想，高效解决固定长度的串式匹配问题。

也可以使用 高级数据结构 Counter，

from collections import Counter
class Solution:def findAnagrams(self, s: str, p: str) -> List[int]:n, m = len(s), len(p)if m > n:return []res = []p_c = Counter(p)for i in range(n-m+1):window = s[i:i+m]if p_c == Counter(window):res.append(i)return res

子串

560. 和为 K 的子数组

思考过程（从暴力到 $O(n)$ 前缀和＋哈希）

1. 暴力枚举

   • 最直观的做法是枚举所有“子数组”$[i..j]$，计算它们的和，看是否等于 $k$。
   • 这需要双重循环，外层 $i$ 从 0 到 $n-1$，内层 $j$ 从 $i$ 到 $n-1$，每次还要再跑一次 $O(n)$ 来累加，则总复杂度 $O(n^3)$（可稍优化到 $O(n^2)$），当 $n$ 很大时无法接受。

2. 引入前缀和

   • 定义前缀和数组 P，其中

     $$P[i]=\sum _{t=0}^{i-1}\mathrm{nums}[t],P[0]=0.$$

   • 那么任意子数组 $\mathrm{nums}[i..j]$ 的和就是

     $$P[j+1]-P[i].$$

   • 若要它等于 $k$，则要有

     $$P[i]=P[j+1]-k.$$

3. 用哈希表统计前缀和出现次数

   • 在一次单遍历中，维护一个哈希表 count，记录「我们已经看到过的」每个前缀和出现的次数。
   • 遍历到位置 j 时，先计算当前前缀和 cur = P[j+1]，再看有多少个之前的前缀和等于 cur - k，这些对应的起点 i 就能让 P[j+1] - P[i] = k。把 count[cur - k] 加到答案里。
   • 然后再把当前前缀和 cur 加入哈希表：count[cur] += 1，以备后续子数组用到它。

4. 细节

   • 初始化：count = {0: 1}，表示空前缀和出现一次。
   • 每步更新和查询都是 $O(1)$，遍历一次数组即可，时间 $O(n)$，空间 $O(n)$。

from collections import defaultdict
def subarray_sum(nums: List[int], k: int) -> int:count = defaultdict(int)count[0] = 1    # 空前缀和出现一次cur = 0         # 当前前缀和 P[j+1]ans = 0for x in nums:cur += xans += count[cur - k]  # 看有多少个 i 使得 P[i] = cur - kcount[cur] += 1  # 记录当前前缀和，以备后续使用return ans

核心精髓：

• 用前缀和把「子数组和」变成两次前缀和之差；
• 哈希表快速统计“之前出现过多少个前缀和等于 当前 - k”，从而一次遍历完成全部子数组计数。

239. 滑动窗口最大值

普通数组

53. 最大子数组和

1. 暴力枚举：

   • 穷举所有子数组 $[i..j]$，累加求和再取最大，需双重循环 $O(n^2)$，当 $n$ 很大时太慢。

2. 能否一次遍历搞定？

   • 观察：一个以 j 结尾的子数组，要么是「接在」之前那个以 j‑1 结尾的最优子数组后面，要么「从头开始」只取 nums[j]。

   • 于是定义「以当前位置结尾的最优子数组和」：

     $${\mathrm{curMax}}_j=\max ({\mathrm{curMax}}_{j-1}+\mathrm{nums}[j],\mathrm{nums}[j]).$$

   • 并维护一个「全局最优」：

     $$\mathrm{best}=\max (\mathrm{best},{\mathrm{curMax}}_j).$$

3. 为什么有效？

   • 如果之前的和是正的，加上当前元素只能让和更大；如果之前的和是负的，与其累加拖后腿，不如重新从当前元素开始。

def max_subarray(nums: List[int]) -> int:cur_max = best = nums[0]  # 初始化：第一项既是“以它结尾的最优”和，也是全局最优for x in nums[1:]:  # 从第二个元素开始，按公式更新cur_max = max(cur_max + x, x)  # 要么接在前面，要么重开一个新子数组best = max(best, cur_max)  # 更新全局最优return best

56. 合并区间

在对所有区间按 左端点从小到大 排序之后，下一步的思考其实很自然：我们只需一次线性扫描，就能把重叠的都“挤”到一起。

1. 准备一个结果列表 merged，用来存放最终不重叠的区间。

2. 遍历已排序的每个区间 [s,e]：

   • 如果 merged 为空，或者 merged 最后一个区间的右端点 < s（没有重叠）， → 直接把当前 [s,e] 追加 到 merged。
   • 否则（有重叠）， → 取 merged 最后一个区间 [ps, pe]，更新它的右端点为 $\max (pe,e)$（因为这两段重叠，合并后右端肯定是二者的更大者）。

3. 遍历结束，merged 里就是所有合并后互不相交的区间了。

def merge(intervals: List[List[int]]) -> List[List[int]]:intervals.sort(key=lambda x: x[0])  # 按左端点排序merged = []# 线性扫描合并for s, e in intervals:if not merged or merged[-1][1] < s:  # 无重叠，直接追加merged.append([s, e])else:merged[-1][1] = max(merged[-1][1], e) # 有重叠，扩大末尾区间的右端点return merged

• 排序：让所有可能重叠的区间都挨着，便于一次性处理。
• “当前” 区间 vs “下一个” 区间：只要它们相交，就把它们看成一个整体；不相交，就是边界，直接分开。
• 线性合并：每次决定的是“到底要 开新段”还是“接到当前段”。

掌握后，任何“合并重叠区间”“压扁区间列表”之类的问题，都能用这一套路：先排，然后一走到底地合并。

189. 轮转数组

核心思路：原地右移整体 k 步相当于：

• 整体翻转

• 前 $k$ 个翻转

• 后 $n-k$ 个翻转

举例

原  [1 2 3 4 5 6 7], k=3
1) 全翻转 → [7 6 5 4 3 2 1]
2) 前 k=3 翻转 → [5 6 7 | 4 3 2 1]
3) 后 n-k=4 翻转→ [5 6 7 | 1 2 3 4]

正是我们想要的结果。

def rotate(nums: List[int], k: int) -> None:n = len(nums)k %= n  # 如果 k>n，等价于 k mod ndef reverse(l: int, r: int):while l < r:nums[l], nums[r] = nums[r], nums[l]l += 1r -= 1reverse(0, n-1)  # 1) 全翻转reverse(0, k-1)  # 2) 前 k 个翻转reverse(k, n-1)  # 3) 后 n-k 个翻转

238. 除自身以外数组的乘积

前缀·后缀乘积拆分：

1. 目标：对于每个位置 i，我们要得到 nums[0…i-1] 的乘积 × nums[i+1…n-1] 的乘积。

2. 不使用除法：不能直接用“总体乘积/nums[i]”，所以要分别算出“左侧乘积”（前缀）和“右侧乘积”（后缀）。

3. 两次遍历：

   • 第一遍（从左到右）：用一个变量 left 维护到当前位置前的前缀乘积，每到 i 就把 left 存进 answer[i]，然后更新 left *= nums[i]。
   • 第二遍（从右到左）：用一个变量 right 维护当前位置后的后缀乘积，每到 i 就把 answer[i] *= right，然后更新 right *= nums[i]。

4. 结果：这样 answer[i] 就是「不包括 nums[i] 的左右两侧乘积」之积。

def product_except_self(nums: List[int]) -> List[int]:n = len(nums)answer = [1] * n# 1) 从左到右，先把前缀乘积写入 answerleft = 1for i in range(n):answer[i] = leftleft *= nums[i]# 2) 从右到左，再乘上后缀乘积right = 1for i in range(n - 1, -1, -1):answer[i] *= rightright *= nums[i]return answer

矩阵

73. 矩阵置零

要想出 原地、$O(mn)$ 的解法，关键在于：

1. 暴力思路回顾

   • 先遍历一遍，记录所有含 0 的行号放到 rows 集合、列号放到 cols 集合。
   • 再遍历一次，对任意 i 属于 rows 或 j 属于 cols 的位置 matrix[i][j] = 0。
   • 时间 $O(mn)$，空间 $O(m+n)$。

• 暴力思路需要额外标记所有要清零的行列（通常用两个集合或额外的矩阵），空间 $O(m+n)$；
• 能不能把这两组标记“挪”到输入矩阵本身里，节省额外空间？

2. 利用矩阵的第一行和第一列当“标记栏”

   • 把 “第 $i$ 行要清零” 的信息，写在 matrix[i][0] 里；
   • 把 “第 $j$ 列要清零” 的信息，写在 matrix[0][j] 里。
   • 第一行/第一列 自己是否要清零，则用额外的两个布尔变量 zero_first_row、zero_first_col 来记录。

这样只用常数个额外变量，就把两组标记存在了输入矩阵的第一行和第一列里，实现了原地 $O(1)$ 额外空间。

def set_zeroes(matrix: List[List[int]]) -> None:if not matrix or not matrix[0]:returnm, n = len(matrix), len(matrix[0])zero_first_row = any(matrix[0][j] == 0 for j in range(n))zero_first_col = any(matrix[i][0] == 0 for i in range(m))# 1) 用第一行/列做标记for i in range(1, m):for j in range(1, n):if matrix[i][j] == 0:matrix[i][0] = 0matrix[0][j] = 0# 2) 根据标记清零内部区域for i in range(1, m):for j in range(1, n):if matrix[i][0] == 0 or matrix[0][j] == 0:matrix[i][j] = 0# 3) 清零第一行（若有必要）if zero_first_row:for j in range(n):matrix[0][j] = 0# 4) 清零第一列（若有必要）if zero_first_col:for i in range(m):matrix[i][0] = 0

优化：把行标记挪到「行首元素」、列标记挪到「列首元素」，只需常数额外变量记录第一行/列自身状态。

链表

# Definition for singly-linked list.
class ListNode:def __init__(self, x):self.val = xself.next = None

160. 相交链表

双指针对齐法，$O(m+n)$ 时间、$O(1)$ 空间：

1. 问题回顾
   两条链表可能有不同的前缀长度，但如果它们相交，从交点到尾部是同一段后缀。我们的目标是 找到这段公共后缀的起点。

2. 长度差对齐思路

   • 如果直接从各自头节点同时走，当较长链表的指针比短链表多迈若干步后，才到达对齐的「同一剩余长度」位置。
   • 常见做法是先 分别计算两链表长度 $m,n$，让长者先走 $|m-n|$ 步，再同步前进，直到相等或都到尾部。

3. 更巧的一步到位：交换头指针

   • 用两个指针 pA、pB 分别从 headA、headB 开始向前走；
   • 当 pA 到末尾时，让它“跳”到 headB 继续走；同理 pB 到末尾后跳到 headA。
   • 这样，两者都走过了 lenA + lenB 步。若存在交点，他们在第二轮必定同时到达交点；否则，两人最终会同时到达 null 并退出。

4. 为什么有效？

   • 假设链表 A 长度 = $m$，B = $n$，交点到尾部的长度 = $t$。
   • 走完一次各自的「独有前缀 + 公共后缀」后，pA 路径长度 = $m$，pB = $n$。
   • 跳到另一链头后，又分别走过对方的整条链。此时 两者路径总长均为 $m+n$。
   • 如果有交点，两个指针在走完 $m+n-t$ 步后就同时抵达交点；若无交点，则均抵达 null。

def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:if not headA or not headB:return NonepA, pB = headA, headB# 当两指针不相等时不断前进；到末尾就切换到另一个列表的头while pA is not pB:pA = pA.next if pA else headBpB = pB.next if pB else headA# 若相交，返回交点；否则两人齐到 None，返回 Nonereturn pA

关键思路提炼

• 对齐长度：让两指针走相同总路程 $m+n$，自然同步到交点或同时到尾端 null。
• 常数空间：整个过程中只用两个指针，无需额外数据结构。

下面是“先算长度、再让长链表指针先走”：

def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:# 1. 计算两条链表长度def length(head: ListNode) -> int:n = 0p = headwhile p:n += 1p = p.nextreturn nlenA = length(headA)lenB = length(headB)# 2. 让 pA / pB 指向较长 / 较短链表的头pA, pB = headA, headB# 3. 长者先走 |lenA - lenB| 步if lenA > lenB:for _ in range(lenA - lenB):pA = pA.nextelse:for _ in range(lenB - lenA):pB = pB.next# 4. 同步向前，找到第一个相同的节点while pA is not pB:pA = pA.nextpB = pB.next# 如果相交，pA/pB 就是交点；否则最终都为 Nonereturn pA

1. 分别遍历 两条链表求长度。
2. 让长链表指针先走 二者长度差步数，这样剩余到尾部的节点数就和短链表相同。
3. 同步后移 两指针，每次一步；第一次相等时即为交点（或同时到 None）。

pA != pB vs pA is not pB： Python 中，一切皆对象，一切变量皆是对象的引用，

• != 调用的是 “不等于” 运算符，底层会调用对象的 __eq__ 方法，然后取反。它关心的是 “值”（或说逻辑上是否相等）。
• is not 则比较的是 “身份”（identity），也就是它们在内存中是否是同一个对象。

在链表相交的场景里，要判断的是「两个指针是否引用了同一个节点对象」——这就是 身份比较，要用 is/is not，而不能用 !=。

206. 反转链表

翻转意味着把每条指针都反过来：原来 curr.next 指向后继 next，要变成指向前驱 prev。

用三个指针维护状态

• prev：指向已处理完并且已反转好的那一段的新尾（初始为 None）；
• curr：指向当前正在处理的节点（初始为 head）；
• nxt：临时存储 curr.next，防止在改指针后丢失“后继”信息。

def reverse_list(head: ListNode) -> ListNode:prev, curr = None, headwhile curr:nxt = curr.next    # 暂存后继节点curr.next = prev   # 翻转指针方向prev = curr        # prev 前移curr = nxt         # curr 前移return prev  # prev 指向反转后链表的头

234. 回文链表

思考过程（O(n) 时间 + O(1) 空间）

关键拆分：把链表分成「前半段」和「后半段」，然后比较它们是否相同。

• 如何找到“中点”：
  • 用快慢指针，快指针一次走两步、慢指针一次走一步；当快指针到尾或越过尾时，慢指针就到了中间。
• 原地翻转后半段：
  • 从中点开始（对于奇数长度跳过中间节点），反转后半链表，使其头指向最后一个节点。
• 比较两段：
  • 用两个指针，一个从头开始，一个从翻转后的后半段开始，同时向后走、比较值。只要全部相等即为回文。

def is_palindrome(head: ListNode) -> bool:if not head or not head.next:return True# 找中点（慢/快指针）slow = fast = headwhile fast and fast.next:slow = slow.nextfast = fast.next.nextif fast:  # 对于奇数长度，跳过中间节点slow = slow.next# 原地翻转后半段prev = Nonecurr = slowwhile curr:nxt = curr.nextcurr.next = prevprev = currcurr = nxt# 对比前半段和翻转后的后半段p1, p2 = head, prevwhile p2:  # 后半段较短，走完即比较完if p1.val != p2.val:return Falsep1 = p1.nextp2 = p2.nextreturn True

141. 环形链表

思考过程（Floyd “龟兔赛跑” 双指针法，$O(n)$ 时间、$O(1)$ 空间）

暴力思路（时间 $O(n)$、空间 $O(n)$）：

• 用一个哈希集合 seen 存已经访问过的节点引用；
• 遍历链表，每遇到一个节点就检查它是否已在 seen 中，若是则有环；否则加入 seen；

如何降低空间至 $O(1)$？

• 观察：如果链表有环，那么从头开始用两根指针，一快一慢同时前进，两者迟早会在环内相遇；

  • 如果无环，fast 最终会走到末尾的 None，循环退出；
  • 如果有环，设从链表头到环入口长度为 $a$，环长为 $c$。快慢指针在环内第 $k$ 步相遇时，满足
    $$2\times (\text{slow 步数})=(\text{fast 步数})\text{且}\text{fast 步数}-\text{slow 步数}\equiv 0(\mathrm{mod}c).$$
    由此能推断它们必然在环里碰面。

def has_cycle(head: ListNode) -> bool:slow = fast = headwhile fast and fast.next:slow = slow.nextfast = fast.next.nextif slow is fast:return Truereturn False

142. 环形链表 II

直接把节点 对象 放到一个集合里——以后 看到同一个节点对象，就说明回到了环里。

class Solution:def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:seen = set()    # 存放已经遍历过的“节点对象”p = headwhile p:if p in seen:return p   # 第一次再次遇到同一个节点对象，就是入环点seen.add(p)p = p.nextreturn None        # 遍历完都没遇到，说明没环

最优做法：Floyd 双指针：如果想把额外空间降到 $O(1)$，可以用龟兔赛跑，

class Solution:def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:slow = fast = head# 1) 检测环while fast and fast.next:slow = slow.nextfast = fast.next.nextif slow is fast:# 2) 找入口p1, p2 = head, slowwhile p1 is not p2:p1 = p1.nextp2 = p2.nextreturn p1return None

• 检测环：快指针走两步，慢指针走一步；相遇说明有环。
• 找入口：相遇后，一个从表头开始，一个从相遇点开始，同速向前，它们相遇的第一个位置就是环的入口。

这两种方法中，用集合的方法更直观易懂，但要 $O(n)$ 额外空间；Floyd 双指针虽然稍微难想一点，却能做到 $O(1)$ 额外空间，面试中也非常常见。

21. 合并两个有序链表

归并思想，类似归并排序的合并一步：

• 核心思路：每次选较小者接在结果尾部

  • 用两个指针 p1 指向 l1 当前待选节点，p2 指向 l2 的当前节点。
  • 在每一步中比较 p1.val 和 p2.val：若 p1.val ≤ p2.val，就把 p1 所指节点连到结果链表尾部，然后 p1 = p1.next；否则就把 p2 的节点连过去，并 p2 = p2.next。这样保证每次都把当前最小的节点“拿出来”拼到新链表末尾。

• 初始化和哨兵节点：为了方便处理“结果链表为空时还没有尾节点”这一边界，通常我们先做一个“哨兵节点”（dummy）指向结果链表头，然后用 tail 指向哨兵，表示“当前结果链表的尾部”。每次选节点后，tail.next = 选中的节点，并 tail = tail.next 把尾指针后移。

• 处理剩余节点：上述循环一直执行到 p1 或 p2 到了 None（至少有一个链表跑完）；此时，另一个链表剩下的部分本身就是有序的，直接 tail.next = p1 or p2（把剩下整段接过去）即可。

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:dummy = ListNode(0)   # 哨兵节点tail = dummy          # tail 指向结果链表的尾部p1, p2 = l1, l2while p1 and p2:if p1.val <= p2.val:tail.next = p1p1 = p1.nextelse:tail.next = p2p2 = p2.nexttail = tail.next# 把未跑完的链表直接接上tail.next = p1 if p1 else p2return dummy.next

这种「归并两个有序序列」的思路，既可以用在链表，也可用在数组，都是算法中非常经典的技巧。

2. 两数相加

模拟小学竖式加法：逐位相加＋跟踪进位：

• 把两个逆序存储的数字看作小学里“从低位到高位”依次相加，每一位都可能产生进位。
• 用变量 carry 保存上一位运算的进位（初始为 0）。

双指针遍历：用 p1、p2 分别指向两条链表的当前节点。在每一步中取出这两个节点的值（若指针已到尾则值视为 0），加上 carry，得到 s = v1 + v2 + carry。

计算当前位和新进位：当前位的结果节点存 s % 10；新的进位 carry = s // 10。

def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:dummy = ListNode(0)tail = dummycarry = 0p1, p2 = l1, l2# 当还有位或有进位时都要继续while p1 or p2 or carry:v1 = p1.val if p1 else 0v2 = p2.val if p2 else 0s = v1 + v2 + carrycarry = s // 10digit = s % 10tail.next = ListNode(digit)tail = tail.nextif p1: p1 = p1.nextif p2: p2 = p2.nextreturn dummy.next

19. 删除链表的倒数第 N 个结点

用两个指针 fast 和 slow，都 从一个哨兵节点（dummy）开始：

dummy → head → … → None↑|
slow, fast

• 先让 fast 向前走 n+1 步，这样 fast 与 slow 之间恰好间隔了 n 个节点。
• 然后同时移动 fast 和 slow，每次各走一步，直到 fast 指向 None（越过尾节点）。这时，slow 正好停在要删除节点的前一个节点上（因为两者间隔 n，fast 已越过最后一个，slow 刚好在倒数第 n+1 个）。
• 让 slow.next = slow.next.next，跳过倒数第 n 个节点，即完成删除。

def removeNthFromEnd(head: ListNode, n: int) -> ListNode:dummy = ListNode(0)dummy.next = headslow = fast = dummy# fast 先走 n+1 步，保证 slow 跟在待删节点前面for _ in range(n + 1):fast = fast.next# 同步前进直到 fast 越过尾部while fast:slow = slow.nextfast = fast.nextslow.next = slow.next.next  # slow.next 就是倒数第 n 个，跳过它return dummy.next

哨兵节点：简化头节点被删的边界情况。

二叉树

94. 二叉树的中序遍历

中序遍历定义：对任意节点 u，先遍历它的 左子树，再访问 自身，最后遍历 右子树，顺序是 “左 → 根 → 右”。

递归与迭代两种思路：

class Solution:# 递归版def inorderTraversal(self, root: TreeNode) -> List[int]:res = []def dfs(u: TreeNode):if not u:returndfs(u.left)res.append(u.val)dfs(u.right)dfs(root)return res# 迭代版def inorderTraversalIter(self, root: TreeNode) -> List[int]:res, stack = [], []u = rootwhile u or stack:while u:stack.append(u)u = u.leftu = stack.pop()res.append(u.val)u = u.rightreturn res

迭代思路（显式栈），用一个栈来模拟递归的“回溯”：

• 从根节点开始，把当前节点 u 一路沿左子链 压栈，直到走到最左的 None。

• 弹出栈顶节点做 访问，然后把它切换到其 右子树，继续重复：“一路压左子链” → 到顶后、“弹栈访问” → 转向右子树

104. 二叉树的最大深度

递归＆迭代两种视角：任何「求树的某种极值度量」的问题，都离不开「分治／递归」或「层序遍历」的思路。

• 定义：depth(u) = 节点 u 为根的子树的最大深度。
• 递推：
  $$\text{depth}(u)=\{\begin{array}{ll}0,& u=\text{None}\\ 1+\max (\text{depth}(u.left),\text{depth}(u.right)),& \text{otherwise}\end{array}$$
• 逻辑：对于任意非空节点，你只需把它左右子树的最大深度算出来，取更大的那个再加 1，就是它的最大深度。
• 终止条件：遇到空指针（None）返回 0。

class Solution:def maxDepth(self, root: TreeNode) -> int:if not root:return 0left_depth  = self.maxDepth(root.left)right_depth = self.maxDepth(root.right)return 1 + max(left_depth, right_depth)

• 时间复杂度：每个节点访问一次 → $O(n)$。
• 空间复杂度：递归栈深度最坏为树的高度 $O(h)$，平均 $O(\log n)$。

另一种思考是「一层一层地往下走，数过了几层就是深度」。

1. 用一个队列 q，初始时把根节点放进去；

2. 维护 depth = 0；

3. 当队列非空时：

   • depth += 1；
   • 本层节点数 sz = len(q)；
   • 循环 sz 次，每次从队头弹出一个节点，将它的左右孩子（若非空）加入队尾。

4. 完成一轮 sz 次弹出／入队，说明我们把这一层都走完了，继续下一层。

5. 当队列空，depth 就是整棵树的最大深度。

from collections import dequeclass Solution:def maxDepth(self, root: TreeNode) -> int:if not root:return 0q = deque([root])depth = 0while q:depth += 1sz = len(q)for _ in range(sz):node = q.popleft()if node.left:q.append(node.left)if node.right:q.append(node.right)return depth

• 时间复杂度：每个节点进队出队各一次 → $O(n)$。
• 空间复杂度：队列最多容纳一层所有节点 → $O(w)$，最坏 $O(n)$，平均 $O(n/2)$。

掌握这两种思路，能快速应对大多数「树的深度／高度／层次」的题目。

• 递归解：自底向上，子问题是「左右子树深度」，合并就是 1 + max(...)。
• 迭代解：BFS 按层遍历，层数即深度。