哈希

查詢流程：哈希→定位→桶內查找，三步均為常數開銷，整體平均 $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 按層遍歷，層數即深度。