Hot 100 全解：按知识点串讲

要完成的任务

给定整数数组 nums 和整数 target，找出两个不同位置，使这两个位置上的数之和等于 target，返回它们的下标。答案中的两个下标可按任意顺序排列。

字段与保证

nums[i] 是下标 i 处的整数；同一个数组元素不能重复使用。题目保证每组输入恰好存在一个有效答案。

全部示例

约束与进阶

• 2 ≤ nums.length ≤ 104。
• -109 ≤ nums[i], target ≤ 109。
• 只存在一个有效答案；进阶要求设计时间复杂度低于 O(n²) 的算法。

暴力：双层循环枚举所有下标对 (i,j)，判 nums[i]+nums[j]==target，O(n²)。瓶颈在内层——每固定一个 x，都要重新扫一遍数组去找它的另一半。

正解：边扫描边建哈希表。
① 定义历史状态：seen 保存“已经扫描过的值 → 下标”，只代表当前位置左侧。
② 计算补数：当前值为 x 时，只需查询 need=target-x，把重复线性查找降为 O(1)。
③ 先查后存：命中就返回 [seen[need], index]；未命中才写入当前值，因此同一元素不会自配。
④ 非平凡样例：[3,3], target=6 中，第一个 3 查空表后写入，第二个 3 才命中前一个下标。

取舍：哈希法用 O(n) 空间把时间从 O(n²) 降到 O(n)；若数组已排序，也可双指针 O(1) 额外空间，但本题还要返回原下标，需额外保留下标映射。

里程碑①  主例开始：nums=[2,7,11,15]，target=9，seen={}
里程碑②  i=0,x=2：need=7 未命中；本轮结束 seen={2:0}
里程碑③  i=1,x=7：need=2 命中历史下标 0；返回 [0,1]
里程碑④  重复值例 [3,3]：第一个 3 先查空表，再写 seen={3:0}
里程碑⑤  第二个 3 查询时尚未写入自身，只会命中下标 0，不会得到 [1,1]

class Solution:
    def twoSum(self, nums, target):
        # 1. seen 只保存当前位置之前的“值 → 下标”
        seen = {}

        # 2. 每轮先查补数，未命中再记录当前值
        for index, value in enumerate(nums):
            complement = target - value
            if complement in seen:
                return [seen[complement], index]
            seen[value] = index
        return []

时间 O(n)，每个元素做一次补数查询并至多写入哈希一次；空间 O(n)，最坏存下几乎所有元素。相比暴力 O(n²) 用 O(n) 空间换来一个数量级的时间提升。

功能：[2,7,11,15],9 → [0,1]；边界：最短两元素 [3,3],6 → [0,1]（重复值也要能命中）；特殊：含负数 [-1,-2,-3],-5 → [1,2]、目标依赖后面元素 [3,2,4],6 → [1,2]（先查后存保证不选到自身）。

考点：哈希表把"查找另一半"降到 O(1)，"先查后存"的顺序细节。关联：↔ LC15 三数之和（两数之和的进阶，固定一个数后转化为两数之和）、↔ LC560 和为K的子数组（同样用哈希查"需要的另一半 = 前缀和 − k"）。

要完成的任务

给定字符串数组 strs，把互为字母异位词的字符串放进同一组并返回所有分组。字母异位词由完全相同的字符及次数组成，只是排列顺序可以不同；分组顺序和组内顺序均不作要求。

全部示例

约束

• 1 ≤ strs.length ≤ 104。
• 0 ≤ strs[i].length ≤ 100，因此空字符串是合法输入。
• strs[i] 只包含小写英文字母。

暴力：两两比较是否互为异位词（各自排序后判等），O(n²·k)，n 个词、词长 k。

正解：规范化指纹 + 哈希分桶。
① 定义等价条件：异位词的字母及出现次数完全相同，只是排列顺序不同。
② 生成稳定指纹：排序法用 ''.join(sorted(word))；仅含小写字母时也可用 tuple(counts)。
③ 按指纹分桶：groups[key].append(word)，最终返回所有桶，无需两两比较。
④ 非平凡样例：eat/tea/ate 都映射到 aet；tan/nat 映射到 ant，两组不会串桶。

取舍：排序指纹代码短，时间 O(n·k log k)；26 位计数指纹时间 O(n·k)，但只适用于字符集已知且固定的场景，并多维护一个计数数组。

strs=["eat","tea","tan","ate","nat","bat"]
里程碑①  groups={}
里程碑②  eat→aet，tea→aet：{aet:[eat,tea]}
里程碑③  tan→ant：{aet:[eat,tea], ant:[tan]}
里程碑④  ate→aet，nat→ant：{aet:[eat,tea,ate], ant:[tan,nat]}
里程碑⑤  bat→abt：形成第三桶；返回三个桶的列表

from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs):
        # 1. 相同排序指纹共享同一个桶
        groups = defaultdict(list)
        for word in strs:
            signature = ''.join(sorted(word))
            groups[signature].append(word)
        return list(groups.values())

from collections import defaultdict

# 计数元组变体：字符集固定为 26 个小写字母
class Solution:
    def groupAnagrams(self, strs):
        groups = defaultdict(list)
        for word in strs:
            # 1. 为当前单词构造不可变的计数指纹
            counts = [0] * 26
            for character in word:
                counts[ord(character) - ord('a')] += 1

            # 2. list 不可哈希，转 tuple 后再归组
            signature = tuple(counts)
            groups[signature].append(word)
        return list(groups.values())

时间 O(n·k log k)，n 个词、每个排序 k log k（k 为词长）；用计数元组当 key 可降到 O(n·k)。空间 O(n·k)，存所有词。

功能：上例 6 词分 3 组；边界：含空串 [""] → [[""]]、单词 ["a"] → [["a"]]；特殊：全部互为异位词 ["abc","bca","cab"] → 一组、无任何异位词全是独立组。

考点：为哈希 key 设计规范化指纹（排序 / 字符计数），异位词的两种判定方式。关联：↔ LC438 找所有字母异位词（同样靠"字符计数相等"判定异位词，但在滑动窗口里动态维护）、↔ LC1 两数之和（同为"用哈希把匹配 O(1) 化"的思路）。

要完成的任务

给定未排序整数数组 nums，返回其中最长“连续整数序列”的长度。这里的连续指数值依次相差 1，元素不要求在原数组中相邻；目标算法需达到 O(n) 时间。

全部示例

约束

• 0 ≤ nums.length ≤ 105，空数组答案为 0。
• -109 ≤ nums[i] ≤ 109。
• 数组可以包含重复值，且输入没有预先排序。

暴力：排序后线扫，相邻连续就 +1、断开就重置，O(n log n)。但题目要 O(n)，排序这一步就超了。

正解：哈希集合 + 只从序列起点扩展。
① 建立集合：values=set(nums) 同时去重，并把成员查询降到均摊 O(1)。
② 识别起点：仅当 value-1 not in values 时，当前值才是一段连续序列的最左端。
③ 向右扩展：从起点不断检查 value+length，直到第一个缺口，再更新最长长度。
④ 非平凡样例：[100,4,200,1,3,2] 中只有 100、200、1 是起点；从 1 一次扩到 4，得到长度 4。

取舍：用 O(n) 集合空间换得均摊 O(n) 时间。虽然代码有嵌套 while，但非起点不会扩展，每个集合元素只属于一段、只被该段访问一次；最坏理论保证仍取决于哈希实现。

nums=[100,4,200,1,3,2] → values={1,2,3,4,100,200}
里程碑①  100 的前驱 99 不在集合：起点，序列 [100]，best=1
里程碑②  4 的前驱 3 在集合：不是起点，跳过
里程碑③  200 的前驱 199 不在集合：序列 [200]，best 仍为 1
里程碑④  1 是起点，连续命中 2、3、4，遇 5 停止
里程碑⑤  本段长度 4，更新 best=4；2、3 后续均因有前驱而跳过

class Solution:
    def longestConsecutive(self, nums):
        # 1. 去重，并支持均摊 O(1) 的成员查询
        values = set(nums)
        longest = 0

        # 2. 只有没有前驱的值才启动一次完整扩展
        for value in values:
            if value - 1 in values:
                continue

            length = 1
            while value + length in values:
                length += 1
            longest = max(longest, length)
        return longest

时间 O(n)，虽有内层 while，但只有起点才进入、每个数被"向上数"访问至多一次；空间 O(n) 存 set。别被双重循环误导成 O(n²)——非起点会被 continue 挡掉。

功能：[100,4,200,1,3,2] → 4；边界：空数组 [] → 0、单元素 [5] → 1；特殊：含重复 [1,2,2,3] → 3（set 去重）、含负数与断层 [0,-1,1] → 3。

考点：用 set 换 O(1) 归属查询，"只从起点计数"避免重复的均摊分析。关联：↔ LC1 两数之和（同为哈希 O(1) 查询）、↔ LC560 和为K的子数组（都是"用哈希把 O(n²) 优化到 O(n)"的经典范例）。

要完成的任务

给定整数数组 nums，把所有 0 移到数组末尾，同时保持所有非零元素原有的相对顺序。必须直接修改输入数组，不能复制出另一份完整数组；返回值为 None，力扣展示的是修改后的 nums。

全部示例

约束与进阶

• 1 ≤ nums.length ≤ 104。
• -231 ≤ nums[i] ≤ 231-1。
• 需要原地完成，并尽量减少写入或交换次数。

暴力：新开一个数组，先按序放入所有非零元素、再补足 0，O(n) 时间但 O(n) 空间，违反"原地"要求。

正解：快慢（读写）指针。只抓住三步：
① 定义待填位：slow 永远指向“下一个非零数该放的位置”。
② 扫描并交换：fast 遇到非零数，就与 slow 位置交换，再让 slow += 1。
③ 遇零跳过：fast 遇到 0 时只继续扫描，等待后面的非零数把它换走。

为什么保序：非零元素被 fast 访问的先后顺序，就是它们在原数组里的先后顺序；而每个非零都被依次放到单调递增的 slow 位置，故相对顺序不变。为什么末尾自然全是 0：fast 扫完后 [0, slow) 装着全部非零，剩下的 [slow, n) 就只能是被换到后面的 0。

样例：[0, 1, 0, 3, 12]      slow = 下一个非零待填位

① 遇到 0：跳过          [0, 1, 0, 3, 12]   slow=0
② 遇到 1：与位置0交换   [1, 0, 0, 3, 12]   slow=1
③ 遇到 3：与位置1交换   [1, 3, 0, 0, 12]   slow=2
④ 遇到12：与位置2交换   [1, 3, 12, 0, 0]   slow=3（完成）

扫完后 [0,3)=[1,3,12] 是保序非零，[3,5)=[0,0] 自然是 0。注意第 1、3 步 slow 停着不动，让 0 攒在 slow 位等着被后面的非零换走。

class Solution:
    def moveZeroes(self, nums):
        # 1. slow 指向下一个非零数应该放入的位置
        slow = 0

        # 2. fast 按原顺序读取；只有读到非零数才写入并推进 slow
        for fast in range(len(nums)):
            if nums[fast] != 0:
                nums[slow], nums[fast] = nums[fast], nums[slow]
                slow += 1

时间 O(n)，单趟扫描；空间 O(1)，原地交换、无额外数组。交换写法天然稳定（保序）。

功能：[0,1,0,3,12] → [1,3,12,0,0]；边界：空 []、单元素 [0] / [1]；特殊：无零 [1,2,3] 不变、全零 [0,0,0]、零在开头/结尾。

考点：快慢（读写）指针做原地覆盖、保序性。关联：↔ LC11 盛最多水的容器（同为双指针但是对撞型，对比同向 vs 对撞）、↔ LC15 三数之和（去重时也用同向指针跳过重复）。

要完成的任务

给定长度为 n 的整数数组 height。第 i 条竖线连接坐标 (i,0) 与 (i,height[i])。选择两条线与 x 轴组成容器，返回能容纳的最大水量；容器不能倾斜。

两线下标为 left、right 时，宽度为 right-left，有效高度由较短线决定，因此面积为 min(height[left],height[right])×(right-left)。

全部示例

约束

• n == height.length，2 ≤ n ≤ 105。
• 0 ≤ height[i] ≤ 104。

暴力：枚举所有线对 (i, j) 求面积取最大，O(n²)。

正解：对撞指针。从最宽的左右两端开始：
① 计算当前面积：min(height[left], height[right]) × (right-left)，较矮的线是容器短板。
② 移动短板：宽度下一步一定变小，只有换掉短板才可能用更高的边弥补宽度损失。
③ 保留最大值：每轮结算一次，直到两指针相遇。

为什么不漏解：每移动一次短板，等于一次性排除掉"以当前短板为一端的所有更窄组合"（它们的宽都比现在小、短板还不变，面积都不会超过刚结算的这个）。所以两指针相向收缩、每根线只经过一次，O(n) 扫完即得全局最优。

height = [1, 8, 6, 2, 5, 4, 8, 3, 7]

① left=0(1), right=8(7)：面积 1×8=8   → 左边矮，left 右移
② left=1(8), right=8(7)：面积 7×7=49  → 更新答案 49，right 左移
③ left=1(8), right=6(8)：面积 8×5=40  → 仍小于 49
④ 后续宽度继续缩小，最大值不再改变

结论：最大容器由下标 1 和 8 围成，答案 49。

注意第 1 步后 left 一直停在 idx1（值 8，全场最高）没再动过——因为之后每一步都是右侧更矮，始终在移 right。移高侧只会更小，正是"移短板"贪心的体现。

class Solution:
    def maxArea(self, height):
        # 1. 从宽度最大的两端开始
        left, right = 0, len(height) - 1
        best_area = 0

        while left < right:
            # 2. 结算当前容器，并保留目前最大面积
            width = right - left
            current_area = min(height[left], height[right]) * width
            best_area = max(best_area, current_area)

            # 3. 宽度必然缩小，所以只移动限制高度的短板
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return best_area

时间 O(n)，两指针共走 n 步；空间 O(1)。贪心正确性：移动高侧不可能变优，故只需移短侧。

功能：[1,8,6,2,5,4,8,3,7] → 49；边界：两条线 [1,1] → 1；特殊：递增 [1,2,3,4] → 4、全等高 [5,5,5] → 10、含 0。

考点：对撞指针 + "移动短板"的贪心正确性证明。关联：↔ LC42 接雨水（同为对撞指针 + 短板思想的进阶）、↔ LC15 三数之和（同用对撞指针在有序数组上收缩）。

要完成的任务

给定整数数组 nums，找出所有三元组 [nums[i],nums[j],nums[k]]，要求三个下标两两不同且三个数之和为 0。返回结果中不能出现重复三元组；三元组内部顺序与结果整体顺序均不作要求。

全部示例

约束

• 3 ≤ nums.length ≤ 3000。
• -105 ≤ nums[i] ≤ 105。
• 输入可以含重复值，但输出按三元组的值去重。

暴力：三重循环枚举所有三元组，O(n³)，还要额外去重。

正解：排序 + 固定一个数 + 对撞指针。
① 排序：让“左指针右移会变大、右指针左移会变小”成立。
② 固定 nums[index]：把三数之和降成在右侧区间寻找两数之和 -nums[index]。
③ 对撞查找：三数和太小就移动 left，太大就移动 right，等于 0 就收集答案。
④ 跳过重复：固定位置以及命中后的左右两端都要去重。

去重是本题灵魂：结果要求三元组之间不重复，而排序后重复值相邻，于是在三个位置各跳过重复——外层 index、命中后的 left、命中后的 right。

排序后：[-4, -1, -1, 0, 1, 2]

① 固定 -4：右侧最大两数和为 1+2=3，连同 -4 仍只有 -1，整轮无解
② 固定 -1：left=-1，right=2  → 和为 0，收集 [-1,-1,2]
③ 继续内缩：left=0，right=1 → 和为 0，收集 [-1,0,1]
④ 下一个 -1 与前一个固定数重复，整轮跳过
⑤ 固定 0：最小组合 0+1+2>0，无解

答案：[[-1,-1,2], [-1,0,1]]

index=0 那轮 left 一路右移始终凑不够（固定数太小），空手而归；index=2 因为和 index=1 同为 −1 被去重整轮跳过——正是这一步避免了重复的 [-1,-1,2]。

class Solution:
    def threeSum(self, nums):
        # 1. 排序后，双指针才具有可控的增减方向
        nums.sort()
        triplets = []

        # 2. 固定第一个数，把问题降为右侧区间的两数之和
        for index in range(len(nums) - 2):
            if nums[index] > 0:
                break
            if index > 0 and nums[index] == nums[index - 1]:
                continue

            left, right = index + 1, len(nums) - 1
            while left < right:
                current_sum = nums[index] + nums[left] + nums[right]

                # 3. 利用有序性调整当前和
                if current_sum < 0:
                    left += 1
                elif current_sum > 0:
                    right -= 1
                else:
                    triplets.append([nums[index], nums[left], nums[right]])
                    left += 1
                    right -= 1

                    # 4. 命中后跳过相同端点，避免重复三元组
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1

        return triplets

时间 O(n²)：排序 O(n log n) + 外层 n × 内层双指针 O(n)。空间 不计输出时，Python list.sort()（Timsort）最坏需要 O(n) 辅助空间；双指针扫描本身只用 O(1)。用哈希也能做，但排序双指针更好去重。

功能：[-1,0,1,2,-1,-4] → [[-1,-1,2],[-1,0,1]]（组内与组间顺序按本实现排序后输出）；边界：不足 3 个元素返回 []；特殊：全零 [0,0,0,0] → [[0,0,0]]（考去重）、无解 [1,2,3] → []、多重复值。

考点：排序 + 固定一维降元 + 对撞指针 + 三处去重。关联：↔ LC1 两数之和（内层就是两数之和，对比哈希 vs 双指针）、↔ LC11 盛最多水的容器（同为有序区间对撞收缩）、↔ LC42 接雨水（同族对撞指针）。

要完成的任务

给定 n 个非负整数 height，每个数表示宽度为 1 的柱子高度。下雨后，水会停在柱子之间且不能高于左右挡板；返回整张高度图能够接住的雨水总量。

全部示例

约束

• n == height.length，1 ≤ n ≤ 2×104。
• 0 ≤ height[i] ≤ 105。

暴力：位置 i 能存的水 = min(左侧最高, 右侧最高) − height[i]；对每个 i 都向左右各扫一遍求两个最高，O(n²)。

解法② 前缀数组。把"每个位置的左边最高、右边最高"预先算好：left_max[index] 从左往右扫（不降的左包络），right_max[index] 从右往左扫（不升的右包络）。之后每格 total_water += min(left_max[index], right_max[index]) − height[index]，O(n) 时间但要 O(n) 额外空间存两条包络线。

正解①：对撞双指针。把两条前缀数组压缩成两个变量：
① 维护左右最高：left_max、right_max 分别记录已经走过区域的最高柱。
② 处理较矮一侧：若左端更矮，右侧已有更高柱兜底，左格水量可立即确定为 left_max-height[left]；反之结算右格。
③ 向中间推进：每格只结算一次，直到指针相遇。

缩小例：[1, 0, 2, 0, 1]      答案 = 2

① 两端同高，先结算右端：水量 0，right→3
② 位置3高度0，右侧最高1：接 1 格水，累计 1
③ 左端高度1小于中间高度2：结算左端 0 格
④ 位置1高度0，左侧最高1：接 1 格水，累计 2
⑤ 指针在高度2处相遇；中间柱贡献必为0，无需单独结算

最终柱高+水位：[1,1,2,1,1]（下标1、3两个凹槽各补 1 格）

缩小例最终 total_water=2；上方原例按同样步骤得到 6。每轮严格按“更新 max → 累加 total_water → 移动一侧指针”的代码顺序执行。

缩小例两法答案都是 2（原例都是 6）。对撞双指针省掉两条包络数组，只保留 left_max/right_max 两个标量。

class Solution:
    def trap(self, height):
        # 1. 从两端向中间走，并记录两侧已经见过的最高柱
        left, right = 0, len(height) - 1
        left_max = right_max = 0
        total_water = 0

        while left < right:
            # 2. 较矮一侧的封顶已经确定，可以立即结算该位置
            if height[left] < height[right]:
                left_max = max(left_max, height[left])
                total_water += left_max - height[left]
                left += 1
            else:
                right_max = max(right_max, height[right])
                total_water += right_max - height[right]
                right -= 1

        return total_water

# 解法二：前缀数组，O(n) 时间、O(n) 空间
class Solution:
    def trap(self, height):
        if not height:
            return 0

        # 1. 分别预处理每个位置两侧（含自身）的最高柱
        length = len(height)
        left_max = [0] * length
        right_max = [0] * length
        left_max[0] = height[0]
        for index in range(1, length):
            left_max[index] = max(left_max[index - 1], height[index])

        right_max[-1] = height[-1]
        for index in range(length - 2, -1, -1):
            right_max[index] = max(right_max[index + 1], height[index])

        # 2. 每格水位由左右包络中较低的一条决定
        total_water = 0
        for index in range(length):
            total_water += min(left_max[index], right_max[index]) - height[index]

        return total_water

解法① 双指针：时间 O(n)，空间 O(1)；当 height[left]<height[right] 时右侧存在更高柱封顶，可安全结算左侧。解法② 前缀数组：时间 O(n)，空间 O(n)，额外保存 left_max/right_max 两条包络。

功能：[0,1,0,2,1,0,1,3,2,1,2,1] → 6；边界：空 / 少于 3 根 [2,0] → 0；特殊：单调递增或递减接不到水 [1,2,3] → 0、平台 [3,0,0,3] → 6。

考点：对撞指针 + "较小侧封顶"的储水思想，能从暴力→前缀数组→O(1) 双指针层层优化。关联：↔ LC11 盛最多水的容器（同为对撞指针 + 短板决定容量）、↔ LC239 滑动窗口最大值（另一类"维护区间极值"的问题，对比单调队列思路）。

要完成的任务

给定字符串 s，返回其中不含重复字符的最长子串长度。子串必须由原字符串中连续的一段字符组成，不能跳过字符拼成子序列。

全部示例

约束

• 0 ≤ s.length ≤ 5×104，空字符串答案为 0。
• s 可由英文字母、数字、符号和空格组成，并非只含小写字母。

暴力起手：枚举所有 (i, j) 子串、检查内部有无重复，O(n³)；即便用一个集合边扩边查也要 O(n²)。瓶颈在于每换一个左端点就把右边重扫一遍，完全没利用"上一个窗口已知无重复"这个信息。

正解：维护一个始终无重复的窗口。
① 右边界扩张：right 每次纳入一个新字符。
② 重复时跳过旧字符：若该字符上次出现的位置仍满足 last[c] >= left，说明旧字符还在窗口内，直接令 left=last[c]+1。
③ 记录当前状态：更新 last[c]，再用合法窗口长度 right-left+1 更新答案。
两个指针都只向右移动，因此每个字符至多进入和离开窗口一次，整体为 O(n)。

用 "abba" 走一遍。
① 读入 a：窗口为 "a"，best=1。
② 读入 b：窗口扩为 "ab"，best=2。
③ 再读 b：旧 b 的下标 1 仍在窗口内，所以 left 跳到 2，窗口缩成 "b"。
④ 最后读 a：旧 a 的下标 0 已在窗口左侧，left 不动，窗口变成 "ba"。这一步说明判断条件不能只写 c in last。

两种实现取舍。
① set 逐格缩：重复时逐个删除左侧字符，逻辑直观。
② dict 下标跳：利用最近下标让 left 一步越过旧字符；同为 O(n)，但没有内层 while，本文采用这一版。

s = "a b b a"      下标 0 1 2 3      初始 left=0, last={}, best=0

r=0 后: [a]          last={a:0},             best=1
r=1 后: [a b]        last={a:0,b:1},         best=2
r=2 读到 b（旧 b=1 仍在窗口）:
  执行 left=2 后: a b [b] a     只移动左边界，last 仍是 {a:0,b:1}
  执行 last[b]=2 后:             last={a:0,b:2}，窗口仍为 "b"
r=3 读到 a（旧 a=0 已在窗口左侧）:
  不执行 left 赋值；执行 last[a]=3 后，窗口为 [b a]，best 仍为 2

class Solution:
    def lengthOfLongestSubstring(self, s):
        # 1. last 记录字符最近位置；[left, right] 始终保持无重复
        last = {}
        left = 0
        best = 0

        # 2. 右扩窗口；只有旧位置仍在窗口内时才移动 left
        for right, char in enumerate(s):
            if char in last and last[char] >= left:
                left = last[char] + 1

            # 3. 记录最新位置，再用当前合法窗口更新答案
            last[char] = right
            best = max(best, right - left + 1)

        return best

时间 O(n)，right 扫一遍、left 只前进；空间 O(min(n, Σ))，Σ 为字符集大小。用"下标跳跃"版比逐格排出的 while 版常数更小。

功能："abcabcbb" → 3、"pwwkew" → 3；边界：空串 "" → 0、单字符 "a" → 1；特殊：全相同 "bbbb" → 1、全不同 "abcdef" → 6、含空格/符号。

考点：变长滑窗维护"无重复"不变式、用哈希记下标实现 left 跳跃。关联：↔ LC438 找所有字母异位词（定长滑窗，对比变长）、↔ LC76 最小覆盖子串（"求最短合法窗口"的滑窗进阶）。

要完成的任务

给定两个字符串 s 和 p，找出 s 中所有长度等于 p.length、且与 p 互为字母异位词的连续子串，返回这些子串的起始下标。答案顺序不作要求。

字母异位词必须拥有完全相同的字符种类与出现次数，只允许排列顺序不同；不同匹配子串可以互相重叠。

全部示例

约束

• 1 ≤ s.length, p.length ≤ 3×104。
• s 与 p 只包含小写英文字母。
• 当 p.length > s.length 时不存在合法窗口，应返回空列表。

暴力起手：对 s 中每个长度为 window_size=len(p) 的起点，取子串排序或计数后与 p 比较，共 n-window_size+1 个窗口、每个 O(window_size log window_size)~O(window_size)，总 O(n·window_size)。浪费在相邻两窗口只差首尾一个字符，却每次从头重算整段计数。

正解：维护长度固定为 window_size 的字符计数。
① 建立目标：need 记录 p 中每个字符需要多少次。
② 平移窗口：每轮只让右侧字符计数 +1、离开的左侧字符计数 -1，中间字符无需重算。
③ 判断命中：当窗口长度为 window_size 且窗口计数与 need 完全相同时，记录窗口左端点。
相邻窗口只更新两个字符，因此扫描 s 一遍即可。

用 s="abab", p="ab" 走一遍。
① 初始窗口 "ab"：计数为 {a:1,b:1}，记录起点 0。
② 平移到 "ba"：右进 a 后暂时超标，再移出旧 a，计数恢复相等，记录起点 1。
③ 平移到 "ab"：右进 b、左出旧 b，计数再次恢复相等，记录起点 2。

两种判定方式。
① Counter 整表比较：每个窗口直接判断 window == need，代码短且不易出错；字符集固定时比较成本可视为 O(26)。
② matches 增量判定：matches 记录当前有多少种字符恰好达标，只有右进和左出的字符可能改变它；字符集较大时更省比较，但边界更容易写错。

matches 什么时候变化？只在计数跨过 need[c] 这个临界值时更新：
① 右进后刚好达标：matches += 1。
② 右进后由达标变超标：matches -= 1。
③ 左出后由超标恢复达标：matches += 1。
④ 左出后由达标变不足：matches -= 1。

s = "a b a b"     p = "a b"     window_size=2     need={a:1,b:1}

初始: [a b] a b       window={a1,b1}           → result=[0]
right=2 先右进 a: [a b a] b   window={a2,b1}   （暂时 3 个字符）
        再左出 a:  a [b a] b   window={a1,b1}   → result=[0,1]
right=3 先右进 b:  a [b a b]  window={a1,b2}
        再左出 b:  a b [a b]  window={a1,b1}    → result=[0,1,2]

注意：右进和左出之间的“超长临时窗口”是真实中间态，不能直接画成平移后的最终窗口。

from collections import Counter

class Solution:
    def findAnagrams(self, s, p):
        # 1. 窗口长度固定为 p 的长度；主串过短时直接结束
        window_size = len(p)
        if len(s) < window_size:
            return []

        # 2. 建立目标计数与第一个定长窗口
        need = Counter(p)
        window = Counter(s[:window_size])
        result = [0] if window == need else []

        # 3. 每轮右进一个字符、左出一个字符，窗口大小保持不变
        for right in range(window_size, len(s)):
            enter_char = s[right]
            leave_char = s[right - window_size]
            window[enter_char] += 1
            window[leave_char] -= 1

            # Counter 比较会保留零计数键，因此减到 0 时必须删除
            if window[leave_char] == 0:
                del window[leave_char]

            # 4. 频次完全相同，记录当前窗口的左端点
            if window == need:
                result.append(right - window_size + 1)

        return result

# 解法二：用 matches 记录“频次恰好达标”的字符种类数
class Solution:
    def findAnagrams(self, s, p):
        # 1. 初始化目标频次和固定窗口状态
        window_size = len(p)
        if len(s) < window_size:
            return []

        need = [0] * 26
        window = [0] * 26
        for char in p:
            need[ord(char) - ord('a')] += 1

        required = sum(1 for count in need if count > 0)
        matches = 0
        result = []

        # 2. 右侧字符进入；只在计数跨过目标值时修正 matches
        for right, char in enumerate(s):
            enter_index = ord(char) - ord('a')
            window[enter_index] += 1
            if need[enter_index] > 0:
                if window[enter_index] == need[enter_index]:
                    matches += 1
                elif window[enter_index] == need[enter_index] + 1:
                    matches -= 1

            # 3. 窗口超长时移出左侧字符，并修正它的达标状态
            if right >= window_size:
                leave_char = s[right - window_size]
                leave_index = ord(leave_char) - ord('a')
                window[leave_index] -= 1
                if need[leave_index] > 0:
                    if window[leave_index] == need[leave_index]:
                        matches += 1
                    elif window[leave_index] == need[leave_index] - 1:
                        matches -= 1

            # 4. 窗口已满且所有目标字符都达标，记录左端点
            if right >= window_size - 1 and matches == required:
                result.append(right - window_size + 1)

        return result

时间 O(n)（字符集固定，Counter 比较视作 O(1)~O(26)）；空间 O(1)，最多 26 个键。删零键是为了让 window==need 成立。

功能：s="cbaebabacd",p="abc" → [0,6]、s="abab",p="ab" → [0,1,2]；边界：len(s)<len(p) 返回 []；特殊：p 全相同 p="aa"、s 中无匹配、s 与 p 等长。

考点：定长滑窗 + 计数数组相等判定异位词。关联：↔ LC49 字母异位词分组（同样"字符计数相等"，但那里是静态哈希分组）、↔ LC3 无重复最长子串（变长 vs 定长滑窗对照）、↔ LC76 最小覆盖子串（同为"窗口计数满足目标"）。

要完成的任务

给定整数数组 nums 和整数 k，统计和恰好等于 k 的非空连续子数组数量并返回。不同起止下标算不同子数组，即使它们包含的值相同。

数组元素允许为负数、0 和正数，所以窗口和不会随边界单调变化，不能直接套只适用于正数数组的滑动窗口。

全部示例

约束

• 1 ≤ nums.length ≤ 2×104。
• -1000 ≤ nums[i] ≤ 1000。
• -107 ≤ k ≤ 107。

暴力起手：子数组由左右端点 (i,j) 确定，枚举所有区间再逐个求和是 O(n³)；预处理前缀和让"求某段区间和"变 O(1)，降到 O(n²)。但固定右端点后，仍要回头找所有满足条件的左端点——这一步能不能也变 O(1)？能，用哈希。

正解：前缀和 + 哈希计数。
① 把区间和改写成两点之差：若当前前缀和为 prefix，某段子数组和为 k，就必须存在更早的前缀和 prefix-k。
② 查询历史：prefix_count[prefix-k] 表示有多少个合法左端点，这些出现次数都要加入答案。
③ 再记录当前前缀：必须先查后存，避免在 k=0 时把当前前缀和自己配对，误算一个空子数组。

用 nums=[1,2,3], k=3 走一遍。
① 初始：prefix=0，预置 prefix_count={0:1}，代表空前缀。
② 读到 1：prefix=1，历史中没有 -2，答案仍为 0。
③ 读到 2：prefix=3，命中历史前缀 0，对应子数组 [1,2]。
④ 读到 3：prefix=6，命中历史前缀 3，对应子数组 [3]，最终答案为 2。

为什么不能用滑动窗口？数组含负数，右端加入新数后窗口和不一定增大，左端移走元素后也不一定减小；“和太大就缩左边”的单调性不存在，因此不能靠双指针排除区间。

nums = [1, 2, 3]，k = 3

第 1 步｜起点：prefix=0，prefix_count={0:1}，answer=0
第 2 步｜读 1：prefix=1，找 -2，未命中              answer=0
第 3 步｜读 2：prefix=3，找  0，命中 [1,2]          answer=1
第 4 步｜读 3：prefix=6，找  3，命中 [3]            answer=2

每次找的是“更早的 prefix-k”；所以本轮必须先查询，再存入当前 prefix。

class Solution:
    def subarraySum(self, nums, k):
        # 1. 空前缀出现一次，用于统计从下标 0 开始的子数组
        prefix_count = {0: 1}
        prefix = 0
        answer = 0

        # 2. 先查询历史 prefix-k，再记录当前 prefix
        for number in nums:
            prefix += number
            answer += prefix_count.get(prefix - k, 0)
            prefix_count[prefix] = prefix_count.get(prefix, 0) + 1

        return answer

时间 O(n)，单趟扫描 + O(1) 哈希；空间 O(n) 存前缀和。count[0]=1 是易错点，用来统计"从下标 0 起就等于 k"的子数组。

功能：[1,1,1],2 → 2、[1,2,3],3 → 2；边界：单元素 [3],3 → 1 / [1],0 → 0；特殊：含负数 [1,-1,0],0 → 3、k=0、全为 0 数组（大量子数组）。

考点：前缀和把区间和转成两点差 + 哈希计数，理解为何有负数不能滑窗。关联：↔ LC1 两数之和（"找 pre−k"就是两数之和的哈希）、↔ LC76 最小覆盖子串（同为子串统计，但用滑窗）。

要完成的任务

给定整数数组 nums 和窗口大小 k。窗口最初覆盖数组最左侧的 k 个元素，此后每次向右移动一格；返回每个窗口中的最大值所组成的数组。

全部示例

约束

• 1 ≤ nums.length ≤ 105。
• -104 ≤ nums[i] ≤ 104。
• 1 ≤ k ≤ nums.length，因此窗口始终有效。

暴力起手：每个窗口从头扫一遍求最大，共 n−k+1 个窗口，O(n·k)。想更快，自然想到用大顶堆维护窗口元素、取最大 O(1)；但元素滑出窗口时堆里删不掉，得存 (值, 下标) 惰性删除，复杂度 O(n log k) 且实现繁。

正解：用单调递减队列保存“仍可能成为最大值”的下标。
① 清理队尾：新元素进入时，队尾所有小于或等于它的旧元素都不可能再成为答案，直接弹出。
② 加入新下标：队列中的值因此始终从队头到队尾递减，队头就是当前最大值。
③ 清理过期队头：若 queue[0] <= right-k，说明该下标已经离开窗口。
④ 记录答案：窗口形成后，把 nums[queue[0]] 加入结果。

为什么存下标而不是值？值只能告诉我们谁大，不能判断它是否已经滑出窗口；下标既能判过期，又能通过 nums[index] 取回值。堆可以做到 O(n log k)，单调队列把每个下标控制为至多入队、出队各一次，因此是 O(n)。

用 [7,2,4], k=2 看两种弹出。
① 窗口 [7,2]：队列为 [7,2]，最大值是队头 7。
② 新元素 4 进入：队尾 2 比 4 小，从队尾弹出。
③ 窗口右移：旧下标 0 的值 7 已过期，从队头弹出；队列只剩 4，第二个最大值为 4。

nums = [7, 2, 4]，k = 2        队列从左到右保持递减

第 1 步｜读 7：queue=[7]，窗口还没满
第 2 步｜读 2：queue=[7,2]，窗口 [7,2] 的最大值是 7
第 3 步｜读 4：先从队尾淘汰 2，queue=[7,4]
第 4 步｜窗口右移：7 从队头过期，queue=[4]，最大值是 4

队尾弹出：新值更有竞争力；队头弹出：旧下标已经离开窗口。

from collections import deque

class Solution:
    def maxSlidingWindow(self, nums, k):
        # 1. queue 存下标，对应值从队头到队尾递减
        queue = deque()
        result = []

        for right, number in enumerate(nums):
            # 2. 淘汰队尾不可能再成为最大值的旧元素
            while queue and nums[queue[-1]] <= number:
                queue.pop()
            queue.append(right)

            # 3. 队头下标离开窗口时，将它移出
            if queue[0] <= right - k:
                queue.popleft()

            # 4. 窗口形成后，队头对应值就是当前最大值
            if right >= k - 1:
                result.append(nums[queue[0]])

        return result

时间 O(n)，每个下标最多入队出队各一次（均摊 O(1)）；空间 O(k)，队列长度不超过窗口。比堆的 O(n log k) 更优。

功能：[1,3,-1,-3,5,3,6,7],3 → [3,3,5,5,6,7]；边界：k=1（返回原数组）、k=len(nums)（返回单个全局最大）；特殊：递减数组 [5,4,3,2],2 → [5,4,3]、含相同值、含负数。

考点：单调队列维护窗口极值、均摊 O(n) 分析、存下标判过期。关联：↔ LC42 接雨水（同为"维护区间最值"，对比对撞指针）、↔ LC3 无重复最长子串（同为定/变长窗口滑动框架）。

要完成的任务

给定字符串 s 和 t，在 s 中寻找最短连续子串，使它包含 t 的全部字符以及各自的重复次数。若不存在返回空字符串；测试数据保证非空答案唯一。

“覆盖”只要求字符计数不少于 t，不要求顺序相同；返回的是子串本身，不是长度或下标。

全部示例

约束与进阶

• m == s.length，n == t.length，且 1 ≤ m,n ≤ 105。
• s 和 t 只由英文字母组成，大小写字符彼此不同。
• 若存在符合条件的子串，题目保证最短答案唯一。
• 进阶要求把时间复杂度做到 O(m+n)。

暴力起手：枚举所有子串 s[i:j]，每个都数一遍是否覆盖 t，O(n²·|Σ|)。观察到：当右端点右移使窗口恰好覆盖 t 后，再往右扩只会更长，此时该缩左端找更短——左右端点都只需单向前进，于是变长滑窗登场。

正解：右扩找可行窗口，左缩寻找最短答案。
① 右边界扩张：不断纳入字符，直到窗口覆盖 t 的全部字符及次数。
② 覆盖后更新答案：当前窗口是一个可行解，先与历史最短窗口比较。
③ 左边界收缩：移出左侧字符，窗口仍覆盖就继续缩；一旦缺少必需字符，再恢复右扩。
④ 两指针单向移动：left 和 right 都不会回退，总移动次数为 O(n)。

如何 O(1) 判断已经覆盖？
① need[c]：表示窗口还缺多少个字符 c；负数表示该字符有富余。
② missing：表示总共还缺多少个必需字符，初值为 len(t)。
③ 纳入字符：只有纳入前 need[c]>0，才真正补上一个缺口并令 missing-=1。
④ 判定覆盖：missing==0 时无需再比较整张计数表，窗口已经覆盖 t。

用 s="ABAAC", t="AAC" 走一遍。
① 右扩到 C：窗口 "ABAAC" 首次覆盖，长度为 5。
② 移出第一个 A：它是富余字符，窗口 "BAAC" 仍覆盖，长度降为 4。
③ 再移出 B：B 不在目标中，窗口 "AAC" 仍覆盖，长度降为 3。
④ 再移出 A：窗口开始缺 A，停止收缩，最短答案就是 "AAC"。

s = A B A A C，t = "AAC"       need 初始 {A:2,C:1}

第 1 步｜右扩到 C：[A B A A C]  首次覆盖，best="ABAAC"
第 2 步｜移出富余 A：A [B A A C] 仍覆盖，best="BAAC"
第 3 步｜移出无关 B：A B [A A C] 仍覆盖，best="AAC"
第 4 步｜再移出 A： A B A [A C]  缺少一个 A，停止收缩

结果：最短覆盖窗口是下标 [2..4] 的 "AAC"。

from collections import Counter

class Solution:
    def minWindow(self, s, t):
        # 1. need 表示各字符还缺多少；missing 表示总缺口
        need = Counter(t)
        missing = len(t)
        left = 0
        best = (float('inf'), 0, 0)

        # 2. 右扩窗口，只有真正补上缺口时才减少 missing
        for right, char in enumerate(s):
            if need[char] > 0:
                missing -= 1
            need[char] -= 1

            # 3. 已覆盖时持续缩左，并记录更短的合法窗口
            while missing == 0:
                window_length = right - left + 1
                if window_length < best[0]:
                    best = (window_length, left, right)

                leave_char = s[left]
                need[leave_char] += 1
                if need[leave_char] > 0:
                    missing += 1
                left += 1

        # 4. best 未更新说明不存在覆盖窗口
        if best[0] == float('inf'):
            return ""
        return s[best[1]:best[2] + 1]

时间 O(|s| + |t|)，left/right 各扫一遍；空间 O(|Σ|) 存计数。need[c] 可为负表示窗口内多余字符，missing 只在补/丢必需字符时变。

功能：s="ADOBECODEBANC",t="ABC" → "BANC"；边界：s=t="a" → "a"、len(s)<len(t) 返回 ""；特殊：t 有重复字符 t="aa"（需两个 a）、无解返回 ""、s 与 t 完全相同。

考点：变长滑窗"右扩找可行 + 左缩求最优"双阶段、用 missing 计数器 O(1) 判覆盖。关联：↔ LC3 无重复最长子串（同为变长滑窗，一个求最长一个求最短）、↔ LC438 找所有异位词（同为"窗口计数满足目标 t"）、↔ LC560 和为K的子数组（同类子串统计的不同工具）。

要完成的任务

给定整数数组 nums，从中选择一个至少包含一个元素的连续子数组，使其元素和最大，返回这个最大和。只返回数值，不需要返回子数组下标。

全部示例

约束与进阶

• 1 ≤ nums.length ≤ 105。
• -104 ≤ nums[i] ≤ 104。
• 必须选择至少一个元素，因此全负数组不能把空子数组当成和 0。
• 进阶要求在 O(n) 解法之外，再尝试分治解法。

暴力：枚举所有 (i,j) 子数组求和取最大，O(n²)（朴素三重循环更是 O(n³)）。

正解①：Kadane / 一维 DP。
① 定义局部状态：current_sum 表示“必须以当前位置结尾”的最大和。
② 决定接续或重开：current_sum=max(value,current_sum+value)；负前缀只会拖累当前值时就丢弃。
③ 记录全局峰值：best_sum 保存所有结尾状态中的最大值，不能只返回最后一个 current_sum。
④ 具体例子：在 [-2,1,-3,4,-1,2,1,-5,4] 中，遇到 4 时重开，随后累加到 [4,-1,2,1] 得到峰值 6。

正解②：分治。把区间答案拆成“完全在左、完全在右、跨中点”三类；跨中点答案等于从中点向左的最大后缀和，加上从中点右侧向右的最大前缀和。

取舍：Kadane 一趟 O(n)/O(1)，首选；分治 O(n log n)（每层把区间劈两半，答案 = max(左半最优, 右半最优, 跨中点最优)）主要练"跨中点合并"的分治思维，比 Kadane 慢，面试写 Kadane 即可。

nums=[-2,1,-3,4,-1,2,1,-5,4]

Kadane 里程碑1  i=0：current_sum=-2，best_sum=-2
里程碑2  i=1：丢弃负前缀，从 [1] 重开；current_sum=1
里程碑3  i=3：再次从 [4] 重开；current_sum=4
里程碑4  i=6：扩成 [4,-1,2,1]；current_sum=best_sum=6
里程碑5  i=8：current_sum=5，但 best_sum 锁住 6

分治顶层 solve(0,8)，middle=4：
左半最优=4，右半最优=4；跨中点左扩峰值=3，右扩峰值=3
合并三类候选：max(4,4,3+3)=6

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 1. 首元素初始化，保证全负数组也必须选一个元素
        current_sum = best_sum = nums[0]

        # 2. 每轮决定接续前段还是从当前值重开
        for value in nums[1:]:
            current_sum = max(value, current_sum + value)
            best_sum = max(best_sum, current_sum)
        return best_sum

# 解法二：分治 O(n log n)（理解分治的经典练习, 比 Kadane 的 O(n) 慢）
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        def solve(left_index, right_index):
            # 1. 单元素区间是递归出口
            if left_index == right_index:
                return nums[left_index]

            # 2. 递归求完全位于左右半区的答案
            middle = (left_index + right_index) // 2
            left_best = solve(left_index, middle)
            right_best = solve(middle + 1, right_index)

            # 3. 从中点两侧向外扩，求跨中点答案
            running_sum = 0
            left_suffix_best = float('-inf')
            for index in range(middle, left_index - 1, -1):
                running_sum += nums[index]
                left_suffix_best = max(left_suffix_best, running_sum)

            running_sum = 0
            right_prefix_best = float('-inf')
            for index in range(middle + 1, right_index + 1):
                running_sum += nums[index]
                right_prefix_best = max(right_prefix_best, running_sum)

            # 4. 三类候选覆盖所有连续子数组
            return max(left_best, right_best, left_suffix_best + right_prefix_best)

        return solve(0, len(nums) - 1)

Kadane：时间 O(n)，空间 O(1)，一次扫描且只用两个滚动变量。分治：时间 O(n log n)，每层合计扫描 O(n)、共 O(log n) 层；空间 O(log n)，来自递归调用栈。

功能：[-2,1,-3,4,-1,2,1,-5,4]→6；边界：单元素 [1]→1、单负元素 [-1]→-1；特殊：全负 [-3,-1,-2]→-1（不能返回0，必须选一个元素）、全正 [1,2,3]→6。

考 Kadane / 一维 DP 的状态设计与"何时重开"。关联：↔ LC152 乘积最大子数组（乘积版需同时维护最大最小值）、↔ LC238 除自身以外的乘积（同为"累积量"思想）。

要完成的任务

给定区间数组 intervals，每个元素 [start,end] 表示包含两个端点的闭区间。合并所有重叠区间，返回一组两两不重叠且覆盖范围相同的区间；输入顺序不保证有序。

全部示例

约束

• 1 ≤ intervals.length ≤ 104，且每项长度为 2。
• 0 ≤ start ≤ end ≤ 104。
• 输出区间的顺序按实现产生即可，标准做法按起点升序返回。

暴力：两两比较，能合并就合并，反复整轮扫描直到没有可合并的对，O(n²) 甚至更糟。

正解：排序 + 一次扫描。
① 按起点排序：排序后，可能继续当前合并段的区间会连续出现。
② 比较结果末尾：当前起点 start 若不大于末尾终点，说明重叠。
③ 扩展或新开：重叠时把末尾终点扩为两者最大值；否则追加新区间。
④ 具体例子：[1,3] 与 [2,6] 合为 [1,6]；下一段 [8,10] 的起点已越过 6，只能新开。

取舍：排序 O(n log n) 主导，扫描 O(n)；相比暴力反复整轮扫描，排序把"找可合并对象"从全局搜索降成"只看相邻"。

输入:   [[1,3],[2,6],[8,10],[15,18]]
排序后: [[1,3],[2,6],[8,10],[15,18]]

里程碑1  结果为空，读 [1,3]：新开 → [[1,3]]
里程碑2  读 [2,6]：2≤3，扩展末尾 → [[1,6]]
里程碑3  读 [8,10]：8>6，新开 → [[1,6],[8,10]]
里程碑4  读 [15,18]：15>10，新开 → [[1,6],[8,10],[15,18]]

最终数轴: 1======6    8==10       15===18

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # 1. 按起点排序，让可能重叠的区间连续出现
        intervals.sort(key=lambda interval: interval[0])
        merged = []

        # 2. 只需与已合并结果的最后一段比较
        for start, end in intervals:
            if merged and start <= merged[-1][1]:
                merged[-1][1] = max(merged[-1][1], end)
            else:
                merged.append([start, end])
        return merged

时间 O(n log n)，排序主导；扫描 O(n)。空间 最坏 O(n)，Python 的 Timsort 可能使用线性临时空间；扫描本身只用 O(1) 辅助状态，返回结果另占 O(n)。

功能：[[1,3],[2,6],[8,10],[15,18]]→[[1,6],[8,10],[15,18]]；边界：单区间 [[1,4]]→[[1,4]]；特殊：仅端点相接 [[1,4],[4,5]]→[[1,5]]（<= 不能写成 <）、被完全包含 [[1,4],[2,3]]→[[1,4]]（终点取 max 才对）、乱序输入。

考"排序+一次扫描"处理区间重叠，以及 <=/取 max 的细节。关联：↔ LC189 轮转数组（同属数组原地/顺序处理）、区间贪心思想可迁移到会议室、插入区间等题。

要完成的任务

给定整数数组 nums 和非负整数 k，把数组整体向右轮转 k 个位置并直接修改 nums。向右轮转一步会把末尾元素移到开头；函数不需要返回新数组。

全部示例

约束与进阶

• 1 ≤ nums.length ≤ 105。
• -231 ≤ nums[i] ≤ 231-1，0 ≤ k ≤ 105。
• 题目鼓励比较至少三种方法，并进一步做到 O(1) 额外空间的原地轮转。

暴力及局限：每次把末尾元素移到开头，重复 k 次需要 O(n·k) 时间；额外数组可用 new[(i+k)%n]=nums[i] 在 O(n) 时间完成，但要 O(n) 空间。

正解：三次翻转。
① 规范位数：k%=n，把完整轮转圈数消掉。
② 整体翻转：[1,2,3,4|5,6,7] 变为 [7,6,5|4,3,2,1]，两段位置已经互换，但各自内部倒序。
③ 修正前段：翻转前 k 个元素，得到 [5,6,7|4,3,2,1]。
④ 修正后段：翻转剩余元素，得到目标 [5,6,7|1,2,3,4]。

具体例子：对 [1,2,3,4,5,6,7], k=3 连续执行“整体翻、前 3 个翻、后 4 个翻”，后 3 个元素恰好稳定移动到数组前方，同时两段内部顺序恢复。

取舍：三次翻转 O(n)/O(1)，实现稳定；额外数组法同为 O(n) 时间但多用 O(n) 空间；环状替换也能 O(1) 空间，却要按 gcd(n,k) 处理多个置换环。

nums=[1,2,3,4,5,6,7], k=3

里程碑1  初始分段：[1,2,3,4 | 5,6,7]
里程碑2  整体翻转：[7,6,5 | 4,3,2,1]
里程碑3  翻前 k 个：[5,6,7 | 4,3,2,1]
里程碑4  翻后 n-k 个：[5,6,7 | 1,2,3,4] ✓

每次交换使用 Python tuple swap，右侧旧值会先整体保存，
不存在“写一半导致旧值丢失”的可观察中间态。

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        length = len(nums)
        k %= length                         # 1. 去掉完整轮转圈数

        def reverse(left, right):
            while left < right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1

        # 2. 整体翻转交换两段位置
        reverse(0, length - 1)
        # 3. 分别翻转两段，恢复各自内部顺序
        reverse(0, k - 1)
        reverse(k, length - 1)

时间 O(n)，三次翻转共约 n 次交换（合计 2n 次元素移动）。空间 O(1)，纯原地。

功能：[1,2,3,4,5,6,7],k=3→[5,6,7,1,2,3,4]；边界：单元素 [1],k=0、k=0 不变；特殊：k>n 如 [1,2],k=3（k%=n 后为1）、k==n（回到原样）。

考原地 O(1) 空间的翻转技巧与 k%=n 取模。关联：↔ LC48 旋转图像（二维版的"翻转组合出旋转"）、↔ LC56 合并区间（同属数组原地处理）。

要完成的任务

给定整数数组 nums，返回同长度数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外所有元素的乘积。要求 O(n) 时间，并且不能使用除法。

全部示例

约束与进阶

• 2 ≤ nums.length ≤ 105。
• -30 ≤ nums[i] ≤ 30；任意前缀或后缀的乘积都保证可用 32 位整数表示，且每个 answer[i] 也保证在 32 位整数范围内。
• 进阶要求除输出数组外仅使用 O(1) 额外空间；返回的输出数组不计入额外空间。

暴力：对每个 i 遍历乘其余元素，O(n²)。除法法：ans[i]=总积/nums[i]，但含 0 会崩(0 处、以及除以 0)，且题目禁止除法。

正解：前缀积 × 后缀积。
① 写入左积：answer[i] 先保存 i 左边所有元素的乘积；当前位置自身不参与。
② 初始化右积：right_product=1，表示最右位置右侧为空集。
③ 合并右积：从右向左先做 answer[i]*=right_product，再把 nums[i] 纳入 right_product。
④ 具体例子：[1,2,3,4] 的左积为 [1,1,2,6]，再依次乘右积得到 [24,12,8,6]。

取舍：两趟扫描 O(n)/O(1) 额外。相比"前缀数组 + 后缀数组"各开一个(也 O(n) 空间)，复用输出数组把额外空间压到 O(1)。

nums = [1,2,3,4]，answer 复用为左积存储，right_product 滚动保存右积

里程碑1  初始化 answer=[1,1,1,1]
里程碑2  左扫完成：answer=[1,1,2,6]
里程碑3  右扫 i=3,2：answer=[1,1,8,6]，right_product=12
里程碑4  右扫 i=1：answer=[1,12,8,6]，right_product=24
里程碑5  右扫 i=0：answer=[24,12,8,6] ✓

每轮必须先写 answer[i]，再更新 right_product，
否则 nums[i] 会错误地乘进自己的答案。

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        length = len(nums)
        answer = [1] * length

        # 1. answer[i] 先保存 i 左边的全部乘积
        for index in range(1, length):
            answer[index] = answer[index - 1] * nums[index - 1]

        # 2. 从右向左乘入右积；先使用，再纳入 nums[index]
        right_product = 1
        for index in range(length - 1, -1, -1):
            answer[index] *= right_product
            right_product *= nums[index]
        return answer

时间 O(n)，两趟扫描。空间 O(1) 额外（输出数组不计）。

功能：[1,2,3,4]→[24,12,8,6]；边界：两元素 [2,3]→[3,2]；特殊：含一个 0 [1,0,3]→[0,3,0]（除自身外含0则为0，唯独0自身位置是其余非0元素之积）、含两个 0 [0,0,3]→[0,0,0]、含负数。

考前缀/后缀积思想与"不用除法+O(1)空间"的构造。关联：↔ LC53 最大子数组和（累积量的一维扫描）、↔ LC152 乘积最大子数组（乘积+可正负的处理）。

要完成的任务

给定未排序整数数组 nums，返回其中没有出现的最小正整数。0、负数和大于数组长度的数都可能出现在输入中；目标复杂度为 O(n) 时间、O(1) 额外空间。

全部示例

约束

• 1 ≤ nums.length ≤ 105。
• -231 ≤ nums[i] ≤ 231-1。
• 数组可含重复值，算法需要原地工作且不能通过额外集合保存所有元素。

暴力：排序后扫 O(n log n)，或哈希集合 O(n) 时间但 O(n) 空间——都不满足"O(n) 时间 + O(1) 空间"。

正解：原地哈希（桶归位）。
① 缩小答案范围：长度为 n 时，答案必在 [1,n+1]；负数、0 和大于 n 的值都不影响最小缺口。
② 把值放回桶：值 value 应放到下标 value-1，让 nums[value-1]=value。
③ 连续归位：交换后当前位置会换入新值，所以必须用 while；目标桶已有相同值时停止，避免重复值死循环。
④ 扫描首个缺口：第一个 nums[i]!=i+1 的位置返回 i+1；若全对齐则返回 n+1。

具体例子：[3,4,-1,1] 依次把 3、4、1 归位，稳定为 [1,-1,3,4]，下标 1 没有值 2，所以答案是 2。

nums=[3,4,-1,1], n=4；值 value 应在下标 value-1

里程碑1  初始：[3,4,-1,1]
里程碑2  i=0，把 3 交换到下标2：[-1,4,3,1]
里程碑3  i=1，把 4 交换到下标3：[-1,1,3,4]
里程碑4  i=1，换入的 1 继续归位：[1,-1,3,4]
里程碑5  扫描：位置0正确；位置1期望2却是-1 → 返回2

交换使用 tuple swap，旧值先整体保存；真正的风险是换入新值后
若只用 if 就不会继续归位，因此代码必须使用 while。

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        length = len(nums)

        # 1. 把 [1,length] 内的值反复交换到 value-1 位置
        for index in range(length):
            while 1 <= nums[index] <= length:
                target_index = nums[index] - 1
                if nums[target_index] == nums[index]:  # 重复值已占目标桶，避免死循环
                    break
                nums[index], nums[target_index] = nums[target_index], nums[index]

        # 2. 第一个值与下标不匹配的位置就是最小缺口
        for index, value in enumerate(nums):
            if value != index + 1:
                return index + 1
        return length + 1

时间 O(n)，每个元素最多被换到正确位置一次（均摊）。空间 O(1)，原地交换。

功能：[3,4,-1,1]→2；边界：[1,2,0]→3、单元素 [1]→2、[2]→1；特殊：全负/越界 [-5,-2]→1、含重复 [1,1]→2（用 nums[nums[i]-1]!=nums[i] 判重防死循环）、[7,8,9,11,12]→1。

考"原地哈希/桶归位"以及 O(1) 空间约束下的抽屉原理。关联：↔ LC287 寻找重复数（同用下标-值映射）、↔ LC189 轮转数组（同为原地操作数组）。

要完成的任务

给定 m×n 整数矩阵 matrix。若某个元素原本为 0，就把它所在的整行和整列全部改为 0；必须直接修改输入矩阵，不返回另一张矩阵。

判断依据必须来自原始矩阵中的 0，不能让置零过程中产生的新 0 再触发额外行列。

全部示例

约束与进阶

• m == matrix.length，n == matrix[0].length，且 1 ≤ m,n ≤ 200。
• -231 ≤ matrix[i][j] ≤ 231-1。
• 直观方案需 O(mn) 标记空间，行列集合需 O(m+n)；进阶要求常量额外空间。

暴力起手：不能边发现 0 边置零——你在 (i,j) 置了 0，往后扫到 (i,j+1) 时又会把这个"新 0"当成原始 0，整行整列被错误扩散。所以先扫一遍记住哪些行、哪些列要清，再统一写。朴素做法：两个集合 rows、cols 存要清的行号列号，O(m+n) 额外空间。

正解：复用首行首列作为标记区。
① 保护原始信息：先用 first_row_zero、first_col_zero 记录首行和首列原本是否含 0，避免后续标记覆盖旧值。
② 扫描内部：遇到 matrix[row][col]==0，先写 matrix[row][0]=0 标记整行，再写 matrix[0][col]=0 标记整列。
③ 回填内部：若某格对应的行标记或列标记为 0，就把该内部格清零。
④ 收尾首行首列：根据预存的两个布尔值决定是否清首行、首列，不能再从已被复用的标记格推断。
⑤ 非平凡样例：唯一 0 在 (1,2) 时，行 1 与列 2 被清零，但首行和首列本身不应整条清零。

取舍：集合标记法更直观但用 O(m+n) 空间；复用首行首列把额外空间降到 O(1)，代价是必须严格遵守“先保存、再标记、后回填、最后收尾”的阶段顺序。

例 matrix=[[1,1,1,1],[1,1,0,1],[1,1,1,1]]
里程碑①  保存首行/首列原始状态：first_row_zero=False，first_col_zero=False
里程碑②  写行标记 matrix[1][0]=0：[[1,1,1,1],[0,1,0,1],[1,1,1,1]]
            此时列标记尚未写，必须保留这个“只完成一半标记”的瞬时态
里程碑③  写列标记 matrix[0][2]=0：[[1,1,0,1],[0,1,0,1],[1,1,1,1]]
里程碑④  根据两类标记回填内部：[[1,1,0,1],[0,0,0,0],[1,1,0,1]]
里程碑⑤  两个首部标志均为 False，不再整清首行/首列，得到最终结果

最终 [[1,1,0,1],[0,0,0,0],[1,1,0,1]]：行1 靠"行标记"整清、(2,2) 靠"列标记"单清，两条标记各司其职 ✓。

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        row_count, col_count = len(matrix), len(matrix[0])

        # 1. 标记区将覆盖旧值，先保存首行首列的原始信息
        first_row_zero = any(matrix[0][col] == 0 for col in range(col_count))
        first_col_zero = any(matrix[row][0] == 0 for row in range(row_count))

        # 2. 扫描内部；行标记与列标记是两次独立写入
        for row in range(1, row_count):
            for col in range(1, col_count):
                if matrix[row][col] == 0:
                    matrix[row][0] = 0
                    matrix[0][col] = 0

        # 3. 只根据标记回填内部，暂不改首行首列
        for row in range(1, row_count):
            for col in range(1, col_count):
                if matrix[row][0] == 0 or matrix[0][col] == 0:
                    matrix[row][col] = 0

        # 4. 最后依据最初保存的状态处理首行首列
        if first_row_zero:
            for col in range(col_count):
                matrix[0][col] = 0
        if first_col_zero:
            for row in range(row_count):
                matrix[row][0] = 0

时间 O(m·n)，每格常数次访问。空间 O(1)，复用首行首列，仅两个布尔变量。

功能：[[1,1,1],[1,0,1],[1,1,1]]→[[1,0,1],[0,0,0],[1,0,1]]；边界：单行 [[1,0,3]]→[[0,0,0]]、单列；特殊：0 在首行/首列 [[0,1],[1,1]]→[[0,0],[0,1]]（考验 first_row/first_col 逻辑）、全 0、无 0 不变。

考"原地标记、避免污染"的技巧与首行首列复用。关联：↔ LC48 旋转图像（同为矩阵原地 O(1) 改写）、↔ LC54 螺旋矩阵（同类二维遍历）。

要完成的任务

给定 m×n 整数矩阵 matrix，从左上角开始，按照顺时针螺旋顺序访问每个元素一次，返回访问顺序组成的数组。输入矩阵不需要被修改。

全部示例

约束

• m == matrix.length，n == matrix[i].length，且 1 ≤ m,n ≤ 10。
• -100 ≤ matrix[i][j] ≤ 100。

暴力起手：真的按方向"走一步、撞墙或撞到走过的格就右转"，需要一个 visited 布尔矩阵判重，O(m·n) 额外空间。

正解：四边界逐圈收缩。
① 定义未访问区：top/bottom/left/right 始终框住尚未输出的矩形。
② 走上边与右边：依次从左到右读顶行、从上到下读右列，随后收缩 top 与 right。
③ 守卫剩余形状：仅当 top<=bottom 时走底边；仅当 left<=right 时走左边，避免单行或单列重复。
④ 重复收圈：每轮最多消去四条边，直到边界交错。
⑤ 非平凡样例：在 2×4 矩阵中，外圈走完上、右、下三条边后已无独立左边，第二个守卫会阻止重复读取。

取舍：方向模拟加 visited 更像实际行走，但需 O(m·n) 额外空间；四边界法只用 O(1) 状态，代价是要仔细维护收缩时机和两个防重复条件。

matrix=[[1,2,3],[4,5,6],[7,8,9]]
里程碑①  边界 (top,bottom,left,right)=(0,2,0,2)，result=[]
里程碑②  走顶边与右边：result=[1,2,3,6,9]，边界变为 (1,2,0,1)
里程碑③  守卫通过，走底边与左边：result=[1,2,3,6,9,8,7,4]
里程碑④  未访问区只剩中心 (1,1)，加入 5
里程碑⑤  边界交错，返回 [1,2,3,6,9,8,7,4,5]

结果 [1,2,3,6,9,8,7,4,5]。第 6 步两个 if 双双拦下——若少了它们，中心 5 那圈会把底行/左列重复读。

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        # 1. 四条边界框住尚未访问的矩形
        top, bottom = 0, len(matrix) - 1
        left, right = 0, len(matrix[0]) - 1
        result = []

        # 2. 每轮按上、右、下、左收完一圈
        while top <= bottom and left <= right:
            for col in range(left, right + 1):
                result.append(matrix[top][col])
            top += 1

            for row in range(top, bottom + 1):
                result.append(matrix[row][right])
            right -= 1

            # 3. 收缩后再判断，防止单行或单列被重复读取
            if top <= bottom:
                for col in range(right, left - 1, -1):
                    result.append(matrix[bottom][col])
                bottom -= 1
            if left <= right:
                for row in range(bottom, top - 1, -1):
                    result.append(matrix[row][left])
                left += 1
        return result

时间 O(m·n)，每个元素恰好写入结果一次。空间 O(1) 额外（不计输出）。

功能：3×3→[1,2,3,6,9,8,7,4,5]；边界：单行 [[1,2,3]]→[1,2,3]、单列 [[1],[2],[3]]→[1,2,3]；特殊：长条形 [[1,2,3,4],[5,6,7,8]]（考验两个 if 边界判断）、1×1 [[7]]→[7]。

考四边界模拟与"防重复"的收缩条件。关联：↔ LC48 旋转图像（同为方向/下标操控）、↔ LC73 矩阵置零（同类二维遍历）。

要完成的任务

给定 n×n 整数矩阵 matrix，把它表示的图像顺时针旋转 90°。必须直接修改原矩阵，不能分配另一张矩阵承接旋转结果；函数无需返回矩阵。

全部示例

约束

• n == matrix.length == matrix[i].length，1 ≤ n ≤ 20。
• -1000 ≤ matrix[i][j] ≤ 1000。
• 矩阵保证为正方形，且必须原地旋转。

暴力起手：另开一个矩阵，按坐标映射 new[j][n-1-i]=old[i][j] 逐格搬。正确但要 O(n²) 额外空间，题目却要求原地。

正解：主对角线转置 + 每行反转。
① 推导目标坐标：顺时针旋转满足 result[row][col]=old[n-1-col][row]。
② 原地转置：只遍历上三角 col>row，交换 (row,col) 与 (col,row)；每一对恰好交换一次。
③ 逐行反转：转置后每行左右翻转，坐标恰好变成目标映射。
④ 非平凡样例：3×3 矩阵先从 [[1,2,3],[4,5,6],[7,8,9]] 转置为 [[1,4,7],[2,5,8],[3,6,9]]，再得到顺时针结果。

取舍：额外矩阵按坐标搬运最直观，但占 O(n²) 空间；转置加反转只用 O(1) 额外空间。逆时针旋转则应转置后做上下翻转，方向不能混用。

里程碑①  原矩阵：[[1,2,3],[4,5,6],[7,8,9]]
里程碑②  交换上三角对 (0,1)↔(1,0)：[[1,4,3],[2,5,6],[7,8,9]]
里程碑③  其余上三角对交换完成：[[1,4,7],[2,5,8],[3,6,9]]
里程碑④  前两行反转：[[7,4,1],[8,5,2],[3,6,9]]
里程碑⑤  最后一行反转：[[7,4,1],[8,5,2],[9,6,3]] ✓
tuple swap 会先保存右侧旧值，不存在可观察的“半次交换”信息丢失态。

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        size = len(matrix)

        # 1. 只交换上三角，确保每个对称位置恰好处理一次
        for row in range(size):
            for col in range(row + 1, size):
                matrix[row][col], matrix[col][row] = matrix[col][row], matrix[row][col]

        # 2. 转置后逐行左右翻转，得到顺时针 90° 结果
        for row in matrix:
            row.reverse()

时间 O(n²)，转置 + 翻转各扫半个/整个矩阵。空间 O(1)，原地交换。

功能：3×3→[[7,4,1],[8,5,2],[9,6,3]]；边界：1×1 [[5]]→[[5]] 不变；特殊：2×2 [[1,2],[3,4]]→[[3,1],[4,2]]、4×4（验证转置 j>i 不重复交换，否则转回去）。

考"转置+翻转拼出旋转"以及只换上三角的细节。关联：↔ LC189 轮转数组（一维翻转组合，同思想）、↔ LC73 矩阵置零（矩阵原地操作）、↔ LC54 螺旋矩阵（二维下标映射）。

要完成的任务

给定 m×n 整数矩阵 matrix 和整数 target，判断 target 是否出现在矩阵中。每一行都从左到右非递减，每一列都从上到下非递减；这不保证按行拼接后整体有序。

全部示例

约束与保证

• m == matrix.length，n == matrix[i].length，且 1 ≤ m,n ≤ 300。
• -109 ≤ matrix[i][j], target ≤ 109。
• 每行从左到右非递减、每列从上到下非递减；元素是否重复不影响算法。

暴力起手：全矩阵扫一遍 O(m·n)，完全没用上"行列都有序"。改进一步：对每一行二分 target，O(m log n)——只用了"行内有序"，还没用上"列也有序"。

正解：从右上角走阶梯。
① 选择枢纽角：右上角同时是当前行最大值、当前列最小值，向左变小、向下变大，两个方向单调性相反。
② 当前值过大：value>target 时，该列从当前位置往下都更大，可整列排除并左移。
③ 当前值过小：value<target 时，该行从当前位置往左都更小，可整行排除并下移。
④ 命中或越界：相等立即返回 True；行或列越界则搜索域为空，返回 False。
⑤ 非平凡样例：在题面 5×5 矩阵中找 5，路径为 15→11→7→4→5：前三次左移排除偏大的列，再下移排除偏小的首行。

取舍：逐行二分是 O(m log n)，实现也清楚；阶梯法同时使用行列有序性，降到 O(m+n)。左下角也可对称实现，而左上/右下两个方向同增或同减，无法唯一决定排除方向。

使用题面 5×5 矩阵，target=5，起点为右上角 (0,4)
里程碑①  (0,4)=15>5：排除第 4 列，左移到 (0,3)
里程碑②  (0,3)=11>5：排除第 3 列，左移到 (0,2)
里程碑③  (0,2)=7>5：排除第 2 列，左移到 (0,1)
里程碑④  (0,1)=4<5：排除第 0 行，下移到 (1,1)
里程碑⑤  (1,1)=5：命中并返回 True
路径 15→11→7→4→5；每一步都永久消去一整行或一整列。

路径 15→11→7→4→5：前三步各砍掉一列、第四步砍掉一行，5 步命中，共走不超过 m+n 格。

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # 1. 从“向左变小、向下变大”的右上角开始
        row, col = 0, len(matrix[0]) - 1

        # 2. 每轮依据比较结果排除一整列或一整行
        while row < len(matrix) and col >= 0:
            value = matrix[row][col]
            if value == target:
                return True
            if value > target:
                col -= 1
            else:
                row += 1
        return False

时间 O(m+n)，每步至少排除一行或一列。空间 O(1)，只用两个指针。

功能：target=5→True；边界：目标位于左下角或右上角、单行或单列矩阵；特殊：不存在 target=20→False（走出边界）、小于全体最小 target=0→False、大于全体最大。

考"利用有序性从枢纽角走阶梯"消去行列。关联：↔ LC54 螺旋矩阵（同为受控的二维行走）、思想上与二分/双指针的"每步缩小搜索域"相通。

要完成的任务

给定两个单链表的头节点 headA 与 headB，返回两条链表开始相交的第一个节点；若没有公共节点则返回 null。相交按节点对象相同判断，不是节点值相等。

输入字段与返回值

intersectVal 只是评测页面展示交点值；skipA、skipB 表示从两条链表头分别走多少步到交点，这三个量都不会传给函数。函数实际只接收两个头节点，且返回后链表结构必须保持不变。

示例 1

示例 2

示例 3

约束与保证

• A、B 的节点数分别为 m、n，且 1 ≤ m,n ≤ 3×10⁴。
• 节点值满足 1 ≤ Node.val ≤ 10⁵；0 ≤ skipA ≤ m，0 ≤ skipB ≤ n。
• 若 intersectVal==0 则两链表不相交；否则它等于 listA[skipA] 与 listB[skipB] 的值。
• 题目保证链表无环，且调用结束后原结构不可被破坏。进阶目标是 O(m+n) 时间、O(1) 额外空间。

暴力：对 A 的每个结点，遍历整个 B 找是否有相同对象，O(m·n)。哈希集优化：把 A 全部结点放进 set，再遍历 B，第一个落在 set 里的结点即答案，O(m+n) 时间但要 O(m) 空间。

正解：双指针换路。关键规律是让两根指针都走完 A+B：
① 各走本链：pa 从 A 出发，pb 从 B 出发。
② 到空换路：pa 到 None 后切到 B 头，pb 到 None 后切到 A 头。
③ 长度对齐：若 A、B 独有段分别长 x、y，两条路线都是 x+y+共享段，长度差被补平。
④ 同一对象收尾：相交时两指针同步落在交点；不相交时同步落在 None，也会退出。

具体例子：A 为 a1→c，B 为 b1→b2→c。pa 走 a1,c,None,b1,b2,c，pb 走 b1,b2,c,None,a1,c，第 5 轮在同一个 c 相遇。

取舍：哈希集直观但费 O(m) 空间;双指针是 O(1) 空间的最优解，代价是要想清"走到头切换对方轨道"和"用 None 收尾"两个细节。

共享结构（c 只存在一个对象）：
A: a1 --------\
                c -> None
B: b1 -> b2 --/

里程碑1  起点：pa=a1，pb=b1
里程碑2  A 先耗尽：pa=None，pb=c
里程碑3  两边完成换路：pa=b2，pb=a1
里程碑4  同步命中：pa=c，pb=c ✓

pa 路线: a1 -> c -> None -> b1 -> b2 -> c
pb 路线: b1 -> b2 -> c -> None -> a1 -> c

class Solution:
    def getIntersectionNode(self, headA, headB):
        # 1. 两指针分别从两条链出发
        pointer_a, pointer_b = headA, headB

        # 2. 到 None 后换到另一条链；相交时同点退出，不相交时同为 None
        while pointer_a is not pointer_b:
            pointer_a = pointer_a.next if pointer_a else headB
            pointer_b = pointer_b.next if pointer_b else headA

        return pointer_a

时间 O(m+n)，两指针各走一遍两链表；空间 O(1)，只用两个指针。

功能：A、B 在中段相交返回该结点；边界：其中一条为空返回 None、相交点即为某条的头；特殊：完全不相交（两指针同时落到 None，循环靠 pa is pb 终止不会死循环）。

考查双指针抵消长度差的技巧、对象身份 vs 值相等的区分。关联：↔ LC141 环形链表（同为双指针路径分析）、↔ LC206 反转链表（都是基础指针操作）。

要完成的任务

给定单链表头节点 head，把每条 next 边反向，并返回反转后的新头节点；空链表仍返回 null。

输入与输出

输入、输出都是链表头节点。题面中的数组只是按 next 顺序展示节点值，不是函数参数。

示例 1

示例 2

示例 3

约束

• 链表节点数在 [0,5000] 内。
• -5000 ≤ Node.val ≤ 5000。

直觉方案：把所有结点压栈，再按出栈顺序重接，能反转但要 O(n) 额外空间；原地改 next 才能降到 O(1)。

正解①：三指针原地反转。
① 保存后继：先令 next_node=cur.next，否则下一步掉头后会丢失余链。
② 当前掉头：cur.next=prev，把当前结点接到已反转段前面。
③ 双指针前进：prev=cur、cur=next_node，重复直到 cur 为空。
④ 返回新头：循环结束时 prev 停在原尾。

正解②：递归回溯。先反转 head.next 起的后段；返回后执行 head.next.next=head 让后继反指当前结点，再用 head.next=None 清掉旧边。若少最后一步，当前结点与后继会形成短环。

取舍：两者都 O(n) 时间。迭代 O(1) 空间、无栈溢出风险，是首选;递归 O(n) 栈空间但代码短，且是理解 24/25 递归解法的基础。

具体例子与优化：处理 1→2→3→4 时，完成节点 2 后现场是 prev=2→1、cur=3，而尚未处理的 3→4 仍由预先保存的后继保持可达。继续同样动作即可得到 4→3→2→1；每步只保存三根指针，把栈方案的 O(n) 空间降为 O(1)。

解法① 迭代，1 -> 2 -> 3 -> None

帧1  初始：prev=None | cur=1 -> 2 -> 3
帧2  保存 next_node=2，再写 1.next=None：
      1 -> None | next_node=2 -> 3   （余链由 next_node 保住）
帧3  反转 2 后：prev=2 -> 1 | cur=3
帧4  反转 3 后：prev=3 -> 2 -> 1 | cur=None

解法② 递归回溯时的短环：
帧1  出口 head=3：3 -> None
帧2  写 3.next=2 后：2↔3（临时短环）；清 2.next 后：3->2
帧3  写 2.next=1 后：1↔2（临时短环）；清 1.next 后：3->2->1

class Solution:
    def reverseList(self, head):
        previous, current = None, head

        # 1. 每轮先保存后继，再让当前结点掉头
        while current:
            next_node = current.next        # 掉头前保住余链
            current.next = previous
            previous, current = current, next_node

        # 2. current 已到空，previous 正好是原尾
        return previous

# 解法二：递归（先反转后段，回溯时掉头）
class Solution:
    def reverseList(self, head):
        # 1. 空链或单结点已经完成反转
        if not head or not head.next:
            return head

        # 2. 先反转后段，回溯时把当前结点接到末尾
        new_head = self.reverseList(head.next)
        head.next.next = head
        head.next = None                  # 清旧边，否则当前结点与后继成环
        return new_head

时间 O(n) 遍历一遍；空间 迭代 O(1)，递归 O(n)（调用栈深度=链长）。

功能：1->2->3 → 3->2->1；边界：空链表返回 None、单结点返回自身；特殊：确认原头结点 next 最终为 None（否则成环）。

考查三指针原地操作、先存后继的意识，是链表面试的基石。关联：↔ LC25 K个一组翻转（分段套用本反转）、↔ LC234 回文链表（反转后半段比对）、↔ LC24 两两交换。

要完成的任务

给定单链表头节点 head，判断从头到尾读出的节点值序列是否为回文，返回布尔值。

输入与输出

数组表示法按链表顺序列出节点值；回文要求正向与反向序列完全相同。

示例 1

示例 2

约束

• 节点数满足 1 ≤ n ≤ 10⁵。
• 0 ≤ Node.val ≤ 9。
• 进阶目标是 O(n) 时间和 O(1) 额外空间。

暴力：把结点值依次倒进数组，再用首尾双指针判回文，O(n) 时间但 O(n) 空间。

正解：找中点 + 反转后半段 + 比对。
① 找中点：slow 每次走 1 步、fast 每次走 2 步；fast 到尾时 slow 停在中点或右中点。
② 反转后半：从 slow 开始原地反转，得到从尾部向中间可走的新头 right_head。
③ 两端比对：left 从原头、right 从 right_head 同步前进，任一值不同立即返回 False。
④ 结构取舍：本法 O(1) 额外空间，但会改动链表；若调用方要求保留原状，比较后再反转一次还原。

为什么奇数长不用特判中点?这份代码让 slow 停在中点，并从 slow 开始反转，所以奇数长时中点包含在反转段里。比对最后一次恰好是“中点和同一个中点对象”相比，必然相等；随后 right 变 None，循环结束，不需要单独跳过或删除中点。

取舍：数组法好写但费 O(n) 空间;本法 O(1) 空间达进阶要求，代价是会改动链表(如需还原，比对后把后半再反转回去)。

具体例子与优化：对 1→2→3→2→1，快慢指针使 slow 停在 3；反转 3→2→1 后，从两端依次比较 1=1、2=2、3=3。只翻转后半段，不需要保存整个值数组。

例：1a -> 2a -> 3 -> 2b -> 1b -> None（a/b 表示不同对象）

帧1  快慢定位：slow 依次 1a→2a→3，停在中点 3
帧2  保存 2b 后写 3.next=None：
      左路 1a->2a->3->None | 余链 2b->1b->None（没有丢链）
帧3  后半反转稳定：right_head=1b->2b->3->None
帧4  比对：1a=1b，2a=2b，最后 3=3（同一中点对象）
帧5  right 耗尽，返回 True

class Solution:
    def isPalindrome(self, head):
        # 1. 快慢指针定位中点或右中点
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # 2. 原地反转从 slow 开始的后半段
        right_head = None
        while slow:
            next_node = slow.next
            slow.next = right_head
            right_head, slow = slow, next_node

        # 3. 以后半段长度为准，从两端同步比对
        left, right = head, right_head
        while right:
            if left.val != right.val:
                return False
            left, right = left.next, right.next
        return True

时间 O(n)：找中点 + 反转 + 比对各 O(n)；空间 O(1)，只在原链表上反转。

功能：偶数 1->2->2->1 True、非回文 1->2->3 False；边界：空/单结点均 True；特殊：奇数长时反转段包含中点，最后中点与自身比较。

考查快慢指针找中点 + 反转的组合。关联：↔ LC206 反转链表（后半段反转）、↔ LC141 环形链表（同为快慢指针）。

要完成的任务

给定链表头节点 head，判断沿 next 不断前进是否会再次到达已经访问过的节点；有环返回 true，无环返回 false。

字段含义

pos 表示尾节点连接到链表中第几个节点（从 0 开始），-1 表示尾节点指向 null。它只用于描述测试数据，不会传入函数。

示例 1

示例 2

示例 3

约束

• 节点数在 [0,10⁴] 内，-10⁵ ≤ Node.val ≤ 10⁵。
• pos 为 -1 或链表中的有效下标。
• 目标是使用 O(1) 额外空间。

暴力：哈希集记录访问过的结点，再次遇到同一对象即有环，O(n) 时间 O(n) 空间。

正解：Floyd 快慢指针。
① 同头出发：slow、fast 都从 head 开始，但初始化相等不能算命中。
② 移动后判断：slow 每轮走 1 步，fast 每轮走 2 步，再比较对象身份。
③ 有环必相遇：两者进入环后，fast 每轮比 slow 多走 1 格，环上距离逐格缩短，最终为 0。
④ 无环会撞尾：fast 或 fast.next 为空时退出；全程只用两根指针。

具体例子与优化：在 3→2→0→-4→2 中，快慢指针进入 2→0→-4 环后，快指针每轮相对多走一格，二者最终在环内同一节点相遇。这个“相对距离每轮减 1”的规律替代了哈希表记录。

结构：3 -> 2 -> 0 -> -4
             ^             |
             +-------------+     （-4.next 回到同一个结点 2）

帧1  初始化：slow=3， fast=3（尚未移动，不判命中）
帧2  第1轮后：slow=2， fast=0
帧3  第2轮后：slow=0， fast=2
帧4  第3轮后：slow=-4，fast=-4，同一对象 ✓

若无环：fast 每步领先, 会先走到 fast.next=None, 循环条件失败退出, 返回 False。

class Solution:
    def hasCycle(self, head):
        slow = fast = head

        # 1. fast 可安全走两步时，再按 1/2 步幅移动
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

            # 2. 必须移动后再判对象身份，避免初始化时误判
            if slow is fast:
                return True
        return False

时间 O(n)：无环走 n/2，有环进环后间距每步 -1 至多绕一圈相遇；空间 O(1)。

功能：有环 True、无环 False；边界：空链表/单结点无环 False、单结点自环 True；特殊：环入口即头结点。

考查 Floyd 判环、为什么快慢必相遇。关联：↔ LC142 环形链表II（进一步求入口）、↔ LC234 回文链表（同快慢指针）。

要完成的任务

给定链表头节点 head，若链表有环，返回从头出发第一次进入环的节点；无环返回 null。不得修改链表。

字段含义

pos 是尾节点所连接节点的 0-based 下标，-1 表示无环；它只描述测试数据，不作为函数参数。评测按返回的节点对象判断答案。

示例 1

示例 2

示例 3

约束与保证

• 节点数在 [0,10⁴] 内，-10⁵ ≤ Node.val ≤ 10⁵。
• pos 为 -1 或链表中的有效下标。
• 题目要求不修改链表；进阶目标是 O(1) 额外空间。

直觉方案：用哈希集记录访问过的对象，第一个重复对象就是入口，O(n) 时间但要 O(n) 空间。

O(1) 空间方案在 141 判环基础上求入口。设 head 到入口距离 a、入口到相遇点距离 b、相遇点绕回入口距离 c(环长 = b+c)。

正解：相遇后再走一趟。
① 找相遇点：先按 LC141 用快慢指针在环内相遇。
② 推出同余：慢指针走 a+b，快指针多走整数圈，故 a=(k-1)(b+c)+c；从 head 到入口的距离，与相遇点沿环到入口的距离同余。
③ 双方同速：新指针 entry 从 head 出发，slow 留在相遇点，两者每次各走一步。
④ 入口相遇：第一次指向同一对象的位置就是环入口。

取舍：也可用哈希集记录首个重复访问结点，O(n) 空间但直白;本法 O(1) 空间，唯一门槛是这段同余推导。

距离关系：head --a--> [入口X] --b--> [相遇点M]
                         ^                     |
                         +---------c-----------+   环长=b+c

具体链：1 -> 2 -> [3] -> 4 -> 5
                    ^              |
                    +--------------+   （5.next 回到同一个 3）

帧1  Floyd 起点：slow=1，fast=1
帧2  两轮后：slow=3，fast=5
帧3  第一次相遇：slow=fast=4（M）
帧4  entry 从 1、slow 从 4 同速走：1/4 → 2/5 → 3/3
帧5  同一对象 3，确定入口 ✓

本例 a=2；M=4 沿环到入口也走 4->5->3 共 2 步，
所以两指针恰好同步到 3。

验证 a=c:a=2(head→入口 3), c=2(相遇点 4 绕回入口:4→5→3), 恰好相等, 印证推导。

class Solution:
    def detectCycle(self, head):
        # 1. Floyd 第一阶段：寻找环内相遇点
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                # 2. 一方从头、一方留在相遇点，同速走到入口
                entry = head
                while entry is not slow:
                    entry = entry.next
                    slow = slow.next
                return entry
        return None

时间 O(n)：找相遇 O(n) + 找入口至多再走 a 步；空间 O(1)。

功能：环入口在中段返回该点；边界：无环返回 None、单结点自环入口=自身；特殊：入口即头结点（a=0，entry 与 slow 起点即相遇）。

考查 Floyd 第二阶段的数学推导。关联：↔ LC141 环形链表（判环基础）、↔ LC287 寻找重复数（把数组下标视为链表用同法找入口）。

要完成的任务

给定两个按非递减顺序排列的单链表 list1 与 list2，把两条链表的现有节点拼接成一条同样有序的链表，并返回合并后头节点。

输入与输出

数组分别展示两条链表从头到尾的节点值；输出数组展示返回头节点沿 next 可访问到的值。

示例 1

示例 2

示例 3

约束与保证

• 两条链表的节点数都在 [0,50] 内。
• -100 ≤ Node.val ≤ 100。
• list1 与 list2 都已按非递减顺序排列。

直觉方案：收集两链所有值、排序后新建链表，时间 O((m+n)log(m+n))、空间 O(m+n)，也浪费了输入已经各自有序的信息。

正解：双指针 + dummy。
① 建立结果尾：dummy 提供固定前驱，tail 始终指向已合并段末尾。
② 比较两头：每轮从 l1、l2 当前头中选更小者接到 tail 后。
③ 前移来源：被选链表的指针前移，tail 跟到刚接入的结点。
④ 拼接余链：一方为空时，另一方剩余段本身有序，整段接上即可。

取舍：迭代 O(1) 空间(复用原结点，不新建);递归写法更短但有 O(m+n) 栈深。相比 LC23 合并 K 路，这里是最基础的两路合并子过程。

具体例子与优化：合并 1→2→4 与 1→3→4 时，当前头依次选 1(l1)、1(l2)、2、3、4(l1)；此时 l1 为空，直接整段接上 l2 剩余的 4。利用已有序性后无需重新排序。

l1: 1a -> 3 -> None      l2: 2 -> None
结果：dummy -> None，tail=dummy

里程碑1  选择 1a：dummy->1a，l1 前移到 3
里程碑2  选择 2 时覆盖 1a 的旧边：
           dummy->1a->2，l1 仍指向 3（因此 3 没丢）
里程碑3  l2 耗尽：tail=2，剩余 l1=3
里程碑4  整段拼接：dummy->1a->2->3->None ✓

class Solution:
    def mergeTwoLists(self, l1, l2):
        # 1. 哨兵统一处理结果链的第一个结点
        dummy = tail = ListNode()

        # 2. 每轮接入两个当前头中的较小者
        while l1 and l2:
            if l1.val <= l2.val:
                tail.next, l1 = l1, l1.next
            else:
                tail.next, l2 = l2, l2.next
            tail = tail.next

        # 3. 一方耗尽后，另一方剩余段可整段接入
        tail.next = l1 or l2
        return dummy.next

时间 O(m+n)，每个结点接一次；空间 O(1)（复用原结点，不新建）。递归写法栈深 O(m+n)。

功能：交替合并；边界：一方为空返回另一方、两方都空返回 None；特殊：一方所有值都小于另一方（尾部整段拼接）、等值元素（<= 保证稳定）。

考查 dummy 哨兵与双指针归并，是归并排序的合并子过程。关联：↔ LC23 合并K个升序链表（两两/堆推广）、↔ LC148 排序链表（归并的合并步）。

要完成的任务

两个非空链表分别以逆序数字表示两个非负整数：头节点是个位，每个节点保存一位。计算两数之和，并用同样的逆序链表返回。

输入与输出

l1、l2 中的每个值都是十进制数字。除数字 0 本身外，输入整数没有前导零；输出也按“个位在头”的方式解释。

示例 1

示例 2

示例 3

约束与保证

• 每条链表的节点数在 [1,100] 内。
• 0 ≤ Node.val ≤ 9。
• 题目保证链表表示的数没有前导零。

直觉方案：先把两条链还原为整数再相加；但超长数字可能溢出，也没有利用“个位在头”的逐位处理顺序。

正解：逐位相加 + 进位。
① 读取本位：逆序链表头就是个位；某一侧耗尽时该位按 0 处理。
② 计算结果：carry,digit=divmod(a+b+carry,10)，商是进位，余数是本位。
③ 追加结点：把 digit 新建为结果结点，tail 与输入指针一起前移。
④ 处理末进位：循环条件包含 carry；例如 5+5 在输入耗尽后还要再追加 1。

取舍：短链走空的一侧当作 0 参与相加(a = l1.val if l1 else 0)，一套循环同时处理"不等长 + 收尾进位"，无需分支特判。

输入：l1: 5 -> None    l2: 5 -> None
初始：dummy -> None，tail=dummy，carry=0

里程碑1  初始化：结果空，carry=0
里程碑2  5+5+0=10：追加 0，carry=1；两输入耗尽
里程碑3  carry 单独触发下一轮：0+0+1=1
里程碑4  追加 1：dummy->0->1，carry=0，结束 ✓
结果 0->1 以逆序表示整数 10。

class Solution:
    def addTwoNumbers(self, l1, l2):
        dummy = tail = ListNode()
        carry = 0

        # 1. 输入或末尾进位尚未耗尽，就继续处理一位
        while l1 or l2 or carry:
            digit_a = l1.val if l1 else 0
            digit_b = l2.val if l2 else 0

            # 2. 商是下一位进位，余数是当前结果位
            carry, digit = divmod(digit_a + digit_b + carry, 10)
            tail.next = ListNode(digit)
            tail = tail.next

            # 3. 较短链耗尽后保持 None，后续按 0 参与
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
        return dummy.next

时间 O(max(m,n))，逐位处理；空间 O(max(m,n)) 存结果链表（进位可能多一位）。

功能：342+465=807；边界：一方明显更长（9->9 + 1）、其中一方为 0；特殊：最高位进位（5+5=10 → 0->1），全靠 carry 留在循环条件里。

考查进位处理与 carry 收尾。关联：LC445 两数相加II（正序存储，用栈或反转）、↔ LC19 删除倒数第N（同用 dummy）。

要完成的任务

给定单链表头节点 head 和整数 n，删除倒数第 n 个节点，并返回删除后的头节点。

输入与输出

n=1 表示删除尾节点，n 等于链表长度时表示删除头节点；题目保证 n 有效。

示例 1

示例 2

示例 3

约束与保证

• 链表节点数 sz 满足 1 ≤ sz ≤ 30。
• 0 ≤ Node.val ≤ 100，且 1 ≤ n ≤ sz。
• 进阶要求只扫描链表一次。

暴力(两趟)：先走一趟数出长度 L，再走到第 L-n 个结点(待删结点的前驱)改指针跳过。正确但扫两遍。

正解：快慢指针固定间距。
① 加哨兵：dummy 让头结点也拥有统一前驱。
② fast 先行：从 dummy 出发先走 n+1 步；多出的 1 步用于让 slow 最终停在目标前驱。
③ 同速到尾：fast、slow 一起走，fast 到 None 时 slow 正好指向待删结点的前驱。
④ 跳过目标：slow.next=slow.next.next，再返回 dummy.next。

具体例子与优化：对 1→2→3→4→5、n=2，fast 从哨兵先走 3 步后停在 3；随后快慢同步，fast 走出链表时 slow 正好停在 3，即待删节点 4 的前驱。固定间距把“两趟计数”优化成一趟扫描。

例：dummy -> 1 -> 2 -> 3 -> 4 -> None，n=2（删结点 3）

里程碑1  fast=slow=dummy
里程碑2  fast 先走 n+1=3 步：
      dummy -> 1 -> 2 -> 3 -> 4 -> None
        slow              fast
里程碑3  同步两轮后：slow=2，fast=None；slow 是 3 的前驱
      dummy -> 1 -> 2 -> 3 -> 4
                         ^
                        slow.next
里程碑4  写 slow.next=slow.next.next 后：
主链：dummy -> 1 -> 2 ----------> 4 -> None
脱链：                    3 ------> 4
                          （3 仍指 4，但已无主链前驱）

class Solution:
    def removeNthFromEnd(self, head, n):
        # 1. 哨兵为头结点提供统一前驱
        dummy = ListNode(0, head)
        fast = slow = dummy

        # 2. fast 先走 n+1 步，让 slow 最终停在待删结点前驱
        for _ in range(n + 1):
            fast = fast.next
        while fast:
            fast, slow = fast.next, slow.next

        # 3. 前驱越过目标结点
        slow.next = slow.next.next
        return dummy.next

时间 O(L) 一趟；空间 O(1)。

功能：删中间结点；边界：删头结点（n=L，靠 dummy）、删尾结点（n=1）；特殊：链表仅一个结点且 n=1（返回 None）。

考查快慢指针固定间距 + dummy 处理删头。关联：LC876 链表中间结点（快慢间距变体）、↔ LC141 环形链表（快慢指针族）。

要完成的任务

给定单链表头节点 head，每两个相邻节点交换一次，并返回交换后的头节点。只能改变节点之间的连接，不能只交换节点值。

输入与输出

数组按 next 顺序展示链表。若最后只剩一个节点，它没有配对对象，应原样留在尾部。

示例 1

示例 2

示例 3

示例 4

约束与保证

• 节点数在 [0,100] 内。
• 0 ≤ Node.val ≤ 100。
• 不得通过修改节点值完成交换。

直觉方案：直接交换相邻结点的值最简单，但题目明确要求交换结点；新建链表则要 O(n) 空间。

正解①：dummy + 前驱指针迭代。
① 取出一对：first=pair_prev.next，second=first.next。
② 保住后段：先写 first.next=second.next，让 first 越过 second 接回余链。
③ 交换并接回：second.next=first，再写 pair_prev.next=second。
④ 前驱前移：pair_prev 移到交换后的组尾 first，继续下一对。

正解② 递归。定理：swapPairs(head) = "交换头两个 first、second，让 first.next 接上 swapPairs(剩余链)，返回 second"。子问题独立，代码更短。

取舍：本题是 LC25 的 k=2 特例。迭代 O(1) 空间为首选;递归 O(n) 栈但直观。

解法① 迭代，交换第一对 1(a)、2(b)
帧1  dummy -> 1(a) -> 2(b) -> 3 -> 4，pre=dummy

写 a.next=b.next 后（a 越过 b；3 暂被 a、b 双重指向）：
      dummy -> 1(a) ---------> 3 -> 4
                     2(b) ----^
                     （b 变量保住脱离主路径的结点 2）

写 b.next=a 后（交换对已成形，但尚未接回 pre）：
      b 路径：2 -> 1 -> 3 -> 4
      主路径：dummy -> 1 -> 3 -> 4
      结点 1 此刻有 dummy 与 b 两个前驱引用

写 pre.next=b 后（稳定态）：
帧4  dummy -> 2 -> 1 -> 3 -> 4，pre 前移到 1

帧5  第二对同法稳定：dummy -> 2 -> 1 -> 4 -> 3 -> None

解法② 递归回溯
帧1  递归先稳定后段：4 -> 3 -> None
帧2  回到首对：1.next=4，再令 2.next=1
帧3  最终：2 -> 1 -> 4 -> 3 -> None

class Solution:
    def swapPairs(self, head):
        dummy = pair_prev = ListNode(0, head)

        # 1. 剩余至少两个结点时，取出当前一对
        while pair_prev.next and pair_prev.next.next:
            first = pair_prev.next
            second = first.next

            # 2. 先让 first 接回后段，再交换本对并接回前驱
            first.next = second.next         # 此步保住后段，顺序不能后移
            second.next = first
            pair_prev.next = second

            # 3. first 已成为本对尾结点
            pair_prev = first
        return dummy.next

# 解法二：递归（交换头两个，后段递归）
class Solution:
    def swapPairs(self, head):
        # 1. 不足两个结点时保持尾段原样
        if not head or not head.next:
            return head

        # 2. first 接递归处理后的后段，second 再反指 first
        first, second = head, head.next
        first.next = self.swapPairs(second.next)
        second.next = first
        return second

时间 O(n)，每对常数次指针操作；空间 迭代 O(1)，递归 O(n)。

功能：1->2->3->4 → 2->1->4->3；边界：空/单结点原样返回；特殊：奇数个结点（最后一个不成对，保持不动）。

考查 dummy + 三指针重接的顺序。关联：↔ LC25 K个一组翻转（本题是 K=2）、↔ LC206 反转链表。

要完成的任务

给定单链表头节点 head 和整数 k，从头开始每 k 个节点组成一组并翻转，返回处理后的头节点；末尾不足 k 个的节点保持原顺序。

输入与输出

只能改变节点连接，不能修改节点值。题目中的数组按 next 顺序展示输入和输出链表。

示例 1

示例 2

约束与保证

• 链表节点数为 n，且 1 ≤ k ≤ n ≤ 5000。
• 0 ≤ Node.val ≤ 1000。
• 末尾不足 k 个节点时必须保持原顺序，进阶目标是 O(1) 额外空间。

直觉方案：每 k 个结点放进栈再倒序接出，逻辑直观，但最坏需要 O(k) 辅助空间；原地翻转可做到 O(1)。

正解：分组翻转（LC206 的推广）。
① 探测整组：从 group_prev 向后走 k 步找 kth；不足 k 个就保持原序并返回。
② 记住边界：group_next=kth.next，它既是下一组头，也是本组翻转的终止位置。
③ 反转本组：按三指针反转，且 prev 初值设为 group_next，让新组尾自动接回后段。
④ 接回前驱：原组头已变组尾；把 group_prev.next 指向 kth，再把 group_prev 移到新组尾。

为什么 prev 初值取 groupNext 而非 None：普通 206 反转到尾时 next 是 None;这里组尾要接的是下一组，所以把"翻转的终点"直接设成下一组头，翻完自动衔接，省一步手动接线。dummy 哨兵统一处理首组前驱。

具体例子与优化：对 1→2→3→4→5、k=3，先确认第 3 个节点存在并记住 group_next=4；翻转时以 4 作为 prev 初值，稳定后直接得到 3→2→1→4→5。尾部只剩 2 个，不足一组便不再动边。

例：dummy -> 1 -> 2 -> 3 -> None，k=2，groupPrev=dummy

帧1  探测够 2 个：kth=2，group_next=3
帧2  组内反转开始：prev=3，cur=1

保存旧后继 2，再写 1.next=3 后：
      dummy -> 1 ---------> 3
                 2 -------^     （3 暂被 1、2 双重指向）
next_node=2 保住尚未处理结点

保存旧后继 3，再写 2.next=1 后：
      cur/prev 路径：2 -> 1 -> 3
      主链仍是：dummy -> 1 -> 3
      （新组头 2 尚未接回 groupPrev）

帧4  接回前驱后：dummy -> 2 -> 1 -> 3 -> None
帧5  下一组只剩 3，不足 k；保持不动并返回 2->1->3

class Solution:
    def reverseKGroup(self, head, k):
        dummy = group_prev = ListNode(0, head)

        while True:
            # 1. 先探测完整一组；不足 k 个时尾段保持原序
            kth = group_prev
            for _ in range(k):
                kth = kth.next
                if not kth:
                    return dummy.next
            group_next = kth.next

            # 2. 仅反转 [group_prev.next, group_next)；prev 从后段头起
            previous, current = group_next, group_prev.next
            while current is not group_next:
                next_node = current.next
                current.next = previous
                previous, current = current, next_node

            # 3. 原组头已成为组尾，接回新组头并移动组前驱
            group_tail = group_prev.next
            group_prev.next = kth
            group_prev = group_tail

时间 O(n)，每个结点被探测 + 翻转常数次；空间 O(1) 迭代。

功能：k=2/k=3 分组翻转；边界：k=1（原样）、k=链长（整体翻转）；特殊：长度非 k 整数倍，末尾不足组保持原序。

链表 Hard 代表：探测够数 + 分段翻转 + 组间重连。关联：↔ LC206 反转链表（组内核心）、↔ LC24 两两交换（k=2 特例）。

要完成的任务

给定一条特殊链表，其中每个节点除 next 外还有可指向链表任意节点或 null 的 random 指针。创建结构完全相同的深拷贝并返回新链表头。

输入表示与深拷贝含义

页面把每个节点写成 [val,random_index]：第二项是 random 所指节点的下标，null 表示不指向节点。新链表中的每个节点都必须是新对象，所有 next/random 也只能指向新链表内部。

示例 1

示例 2

示例 3

约束与保证

• 节点数 n 在 [0,1000] 内。
• -10⁴ ≤ Node.val ≤ 10⁴。
• random 为 null 或指向当前链表中的某个节点。

难点：拷贝某结点时，它的 random 目标可能还没被创建，没法直接指过去。

正解①：哈希映射。
① 建对象：第一趟为每个原结点创建拷贝，记录 old_to_new[old]=copy。
② 翻译引用：第二趟把原 next/random 的目标通过映射换成对应拷贝；所有对象已建齐，不怕前向 random。

正解②：原地交织。
① 插入拷贝：把 X' 放在 X 后，形成 A→A'→B→B'。
② 连接 random：若 X.random=T，则 X'.random=T.next，因为 T' 就在 T 后。
③ 拆分两链：逐对恢复原 next，并把拷贝结点串起来，确保两条链完全解耦。

取舍：两者都 O(n) 时间。哈希法好写好想，是首选;交织法省下 O(n) 空间但要小心拆分时彻底还原原链的 next(否则破坏输入)。

具体例子与优化：若原节点 A 的 random 指向 C，交织后局部为 A→A'→…→C→C'，所以无需哈希查找，直接令 A'.random=C.next=C'。这一固定邻接关系把映射空间从 O(n) 降为 O(1)。

原链：A -> B -> None，A.random=B，B.random=A

解法② 原地交织
帧1  插入全部拷贝：A -> A' -> B -> B' -> None
帧2  利用“原目标的 next 就是目标拷贝”连接 random：
原 A.random ─────> B       所以 A'.random ─────> B'
原 B.random ─────> A       所以 B'.random ─────> A'

帧3  拆分 A/A'：先写 A.next=B
      原入口 A -> B -> B'
      拷贝入口 A' -> B       （仍暂时跨回原链）
      再写 A'.next=B' 后：
      原入口 A -> B -> B'
      拷贝入口 A' -> B'      （拷贝链已局部独立）

帧4  拆分 B/B' 后：原链 A->B；拷贝链 A'->B'，互不共享对象 ✓

解法① 哈希映射
第一趟：{A:A', B:B'}（只建新对象）
第二趟：A'.next=B'，A'.random=B'；B'.next=None，B'.random=A'

# 解法二：原地交织（O(1) 辅助空间，三趟）
class Solution:
    def copyRandomList(self, head):
        if not head:
            return None

        # 1. 在每个原结点后插入对应拷贝
        current = head
        while current:
            current.next = Node(current.val, current.next)
            current = current.next.next

        # 2. 原 random 目标的 next，就是该目标的拷贝
        current = head
        while current:
            if current.random:
                current.next.random = current.random.next
            current = current.next.next

        # 3. 同时还原原链并串起拷贝链
        current = head
        copy_head = head.next
        while current:
            copy_node = current.next
            current.next = copy_node.next
            copy_node.next = copy_node.next.next if copy_node.next else None
            current = current.next
        return copy_head

# 解法一：哈希表映射法（O(n) 空间，两趟）
class Solution:
    def copyRandomList(self, head):
        if not head:
            return None

        # 1. 第一趟只创建对象，保证所有引用目标都已有拷贝
        old_to_new = {}
        current = head
        while current:
            old_to_new[current] = Node(current.val)
            current = current.next

        # 2. 第二趟把 next 与 random 都翻译到新对象
        current = head
        while current:
            old_to_new[current].next = old_to_new.get(current.next)
            old_to_new[current].random = old_to_new.get(current.random)
            current = current.next
        return old_to_new[head]

时间 O(n) 三趟；空间 交织法 O(1)（不含输出），哈希法 O(n)。

功能：random 指向前/后结点均正确复制；边界：空链表返回 None、单结点 random 指自身；特殊：所有 random 为 None、random 成环。

考查深拷贝、交织拆分技巧。关联：LC133 克隆图（同为带引用结构的深拷贝，用哈希映射）、↔ LC2 两数相加（同为新建结点）。

要完成的任务

给定单链表头节点 head，按节点值从小到大排序，并返回排序后的链表头节点。

输入与输出

数组按 next 顺序展示节点值；输出仍是一条链表，而不是数组。

示例 1

示例 2

示例 3

约束

• 节点数在 [0,5×10⁴] 内。
• -10⁵ ≤ Node.val ≤ 10⁵。
• 进阶目标是 O(n log n) 时间和 O(1) 额外空间。

直觉方案：把结点值放入数组排序再写回，时间 O(n log n)、空间 O(n)，没有利用链表可通过断链和拼接完成原地归并。

为什么归并最契合链表：快排要按下标随机访问定位 pivot 两侧，链表做不到 O(1) 随机访问;而归并排序只需要"顺序遍历 + 断开/拼接指针"，正是链表擅长的，且合并两段有序链不需要额外数组(复用 21 的双指针)。

正解：自顶向下归并。
① 找中点：slow 从 head、fast 从 head.next 出发，让 slow 停在前半末尾。
② 保存并断开：先保存 right_head=slow.next，再写 slow.next=None，保证两段都变短且不丢右段。
③ 递归排序：分别排序左右两段，直到长度 0/1。
④ 合并有序段：复用 LC21 的双指针归并。

为什么找中点 fast 从 head.next 起：这样偶数长时 slow 停在前半的最后一个，slow.next 才能把链断成两段都非空;若 fast 从 head 起，两个结点的链会切成"整条 + 空"导致无限递归。

取舍：自顶向下递归有 O(log n) 栈空间;要真正 O(1) 空间得用自底向上(按子段长 1,2,4,… 迭代两两合并)。面试自顶向下足够，代码更清晰。

输入：3 -> 1 -> 2 -> None

帧1  顶层保存 right_head=2，再写 slow.next=None：
      左：3 -> 1 -> None      右：2 -> None

帧2  左段继续分割：保存 1，再断开 3.next
      左左：3 -> None         左右：1 -> None

帧3  merge(3,1) 稳定返回：1 -> 3

帧4  最终 merge 接入 2 时覆盖旧边 1->3：
      dummy -> 1 -> 2 -> None      l1 -> 3
      （结点 3 没丢，由 l1 引用保住）
帧5  接上剩余段：dummy -> 1 -> 2 -> 3 -> None ✓

class Solution:
    def sortList(self, head):
        # 1. 空链或单结点天然有序
        if not head or not head.next:
            return head

        # 2. fast 领先一步，使 slow 停在前半段末尾
        slow, fast = head, head.next
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
        right_head = slow.next             # 断链前先保存右半段
        slow.next = None

        # 3. 递归排序左右两段，再归并
        left = self.sortList(head)
        right = self.sortList(right_head)
        return self._merge(left, right)

    def _merge(self, left, right):
        # 4. 复用原结点归并两条有序链
        dummy = tail = ListNode()
        while left and right:
            if left.val <= right.val:
                tail.next, left = left, left.next
            else:
                tail.next, right = right, right.next
            tail = tail.next
        tail.next = left or right
        return dummy.next

时间 O(n log n)：log n 层，每层合并 O(n)；空间 自顶向下 O(log n) 栈，自底向上 O(1)。

功能：乱序 4->2->1->3 → 1->2->3->4；边界：空/单结点、已有序、逆序；特殊：含重复值（<= 保稳定）、含负数。

考查链表归并排序（分割 + 合并）。关联：↔ LC21 合并两个有序链表（合并子过程）、↔ LC23 合并K个升序链表（分治思想相通）。

要完成的任务

给定包含 k 条链表的数组 lists，每条链表都按升序排列。把所有节点合并成一条升序链表，并返回其头节点。

输入与输出

外层数组表示链表集合，内层数组按 next 顺序展示一条链表；空内层数组表示空链表，空外层数组表示没有任何链表。

示例 1

示例 2

示例 3

约束与保证

• k==lists.length，且 0 ≤ k ≤ 10⁴。
• 每条链表长度在 [0,500] 内；-10⁴ ≤ Node.val ≤ 10⁴。
• 每条链表按升序排列，所有链表的节点总数不超过 10⁴。

暴力：逐条往结果里 merge，第 i 次合并代价约 O(i·avg)，累计 O(k²·avg) = O(kN)。慢在"越合越长的结果被反复重扫"。

正解①：最小堆。
① 放入候选：每条非空链只把当前头放进堆。
② 弹出最小：堆顶一定是所有未合并结点中的最小可选值，把它接到结果尾。
③ 后继补位：若弹出结点还有 next，就把后继入堆；堆大小始终不超过 k。
④ 直到堆空：每个结点入堆、出堆各一次，时间 O(N log k)。

正解②：分治两两合并。把 k 条链按区间对半递归，左右各自合并后再做一次 LC21；共 log k 层，每层合计扫描 N 个结点。

取舍：堆法直观好写、空间 O(k);分治法空间 O(log k) 递归栈、常数更小。两者时间同阶，面试任选其一讲透即可。

具体例子与优化：对 [1,4,5]、[1,3,4]、[2,6]，堆中最初只放三个链头 1、1、2；弹出第一个 1 后仅补入它的后继 4，而不是一次放入全部节点。堆大小始终不超过 k，单次选择从 O(k) 降为 O(log k)。

解法① 最小堆，lists=[1a->4, 2b, 3c]
帧1  初始堆：[1a,2b,3c]，结果为空
帧2  弹 1a 并补入 4：结果 1a，堆=[2b,3c,4]
帧3  弹 2b；tail.next=2b 会覆盖旧边 1a->4：
      结果：dummy -> 1a -> 2b -> None
      堆：[3c,4] -----------------> 4（所以旧后继没有丢）
帧4  弹 3c：结果 1a->2b->3c，堆=[4]
帧5  弹 4：结果 1a->2b->3c->4，堆空 ✓

解法② 分治两两合并, k=4: lists = [A, B, C, D]
第0层:  A    B     C    D
         \  /       \  /
         merge      merge          每次 merge 两条有序链
           |          |
第1层:    AB         CD             (剩 2 条)
             \      /
              merge                log2(4)=2 层
                |
              ABCD                 (剩 1 条, 完成)

递归: solve(0,3) = merge( solve(0,1), solve(2,3) )
每层所有 merge 合计遍历 O(N), 共 log k 层 → O(N log k)

具体 merge(1->3, 2) 的结构帧：
接 1：dummy -> 1 -> 3，变量 a 前移后仍指 3
接 2：dummy -> 1 -> 2；旧边 1->3 被覆盖，但 a 保住 3
接余段：dummy -> 1 -> 2 -> 3

import heapq

class Solution:
    def mergeKLists(self, lists):
        # 1. 每条非空链只放入当前头；index 负责等值时兜底比较
        heap = []
        for index, node in enumerate(lists):
            if node:
                heapq.heappush(heap, (node.val, index, node))

        # 2. 每次输出全局最小头，并用其后继补位
        dummy = tail = ListNode()
        while heap:
            _, index, node = heapq.heappop(heap)
            tail.next = node
            tail = node
            if node.next:
                heapq.heappush(heap, (node.next.val, index, node.next))
        return dummy.next

# 解法二：分治两两合并，O(N log k) 时间 / O(log k) 递归栈
class Solution:
    def mergeKLists(self, lists):
        if not lists:
            return None

        def merge(left, right):
            # 1. 合并两条有序链
            dummy = tail = ListNode()
            while left and right:
                if left.val <= right.val:
                    tail.next, left = left, left.next
                else:
                    tail.next, right = right, right.next
                tail = tail.next
            tail.next = left or right
            return dummy.next

        def solve(left_index, right_index):
            # 2. 显式递归区间；单链是分治出口
            if left_index == right_index:
                return lists[left_index]
            middle = (left_index + right_index) // 2
            left_result = solve(left_index, middle)
            right_result = solve(middle + 1, right_index)
            return merge(left_result, right_result)

        return solve(0, len(lists) - 1)

时间 O(N log k)：N 个结点各入堆/出堆一次，堆大小 ≤ k；空间 O(k) 堆。分治法时间同，空间 O(log k) 栈。

功能：3 条链交替合并；边界：lists=[] 返回 None、含空链表（跳过不入堆）、k=1；特殊：等值元素（元组第二元 i 做 tie-breaker，避免比较 ListNode 报错）。

考查堆/分治、以及元组 tie-breaker 避免比较结点对象。关联：↔ LC21 合并两个有序链表（k=2 基础）、↔ LC148 排序链表（分治合并同源）。

要完成的任务

实现 LRUCache：构造时给定正整数容量 capacity；get(key) 返回键对应的值，不存在则返回 -1；put(key,value) 更新或插入键值。插入新键且容量已满时，删除最久未使用的键。

操作语义

一次成功的 get 或任意 put 都会把该键变成最近使用；更新已有键不增加缓存条目数。构造函数和 put 没有返回值，页面用 null 表示。

示例

约束与保证

• 1 ≤ capacity ≤ 3000。
• 0 ≤ key ≤ 10⁴，0 ≤ value ≤ 10⁵。
• 最多调用 2×10⁵ 次 get 和 put。
• 两种操作都必须达到平均 O(1) 时间复杂度。

暴力/单结构局限：只用哈希表能 O(1) 定位，却不知道谁最久未用；只用链表能记录新旧顺序，按 key 查找却要 O(n)。

正解：哈希表 + 双向链表。
① 定位结点：cache[key] O(1) 找到对象。
② 维护新旧：链表 head 后是最近使用，tail 前是最久使用。
③ 刷新访问：get 命中或 put 更新，都先摘除结点再插到头部。
④ 超容淘汰：删除 tail.prev，并同步删除哈希映射。

为什么必须双向：拿到中间结点后，双向链表能直接访问前驱并 O(1) 摘除；单向链表仍需从头找前驱。两端哨兵保证插入/删除时邻居始终存在。

具体例子与优化：容量 2 时依次 put(1,1)、put(2,2) 后顺序为 2→1；get(1) 把它移到头，变成 1→2；再插入 3 就从尾部 O(1) 淘汰键 2。哈希负责定位，双链表负责顺序，两种 O(1) 操作各司其职。

cap=2；H 后是最近，T 前是最久

帧1  初始化：H <=> T
帧2  put(1)：插头中先改 T.prev=1，此时 H.next 仍是 T（双向暂不对称）；
      再改 H.next=1，稳定为 H <=> 1 <=> T
帧3  put(2)：H <=> 2 <=> 1 <=> T
帧4  get(1)：摘除时先改 2.next=T，T.prev 暂仍是 1；补写 T.prev=2 后脱链；
      再插头，稳定为 H <=> 1 <=> 2 <=> T
帧5  put(3) 暂超容：H <=> 3 <=> 1 <=> 2 <=> T
      淘汰 2 后：H <=> 3 <=> 1 <=> T，keys={1,3} ✓

class Node:
    def __init__(self, key=0, value=0):
        self.key, self.value = key, value
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity):
        # 1. 哈希负责定位，双链负责维护最近/最久顺序
        self.capacity = capacity
        self.cache = {}
        self.head, self.tail = Node(), Node()
        self.head.next, self.tail.prev = self.tail, self.head

    def _remove(self, node):
        # 2. 双向引用让中间结点可 O(1) 摘除
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_front(self, node):
        # 3. 插到 head 后，表示最近使用
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._add_front(node)
        return node.value

    def put(self, key, value):
        # 4. 已存在时原地更新并刷新，不增加容量
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self._remove(node)
            self._add_front(node)
            return

        node = Node(key, value)
        self.cache[key] = node
        self._add_front(node)

        # 5. 超容量时淘汰 tail 前的最久未用结点
        if len(self.cache) > self.capacity:
            least_recent = self.tail.prev
            self._remove(least_recent)
            del self.cache[least_recent.key]

时间 get/put 均 O(1)（哈希定位 + 常数指针操作）；空间 O(capacity)。

功能：put/get 命中刷新顺序；边界：capacity=1（每次 put 新键都淘汰旧键）、get 不存在返回 -1；特殊：put 已存在的 key 更新值并刷新为最近（不算新增、不触发淘汰）。

高频设计题：哈希 + 双向链表复合结构、为什么必须双向。关联：LC460 LFU缓存（频次维度，哈希套双链表）、↔ LC206 反转链表（同为指针重接基本功）。

要完成的任务

给定二叉树根节点 root，按“左子树 → 根节点 → 右子树”的中序顺序访问所有节点，并返回节点值列表。

输入表示

题面用层序数组展示树，null 表示对应孩子不存在；函数实际接收根节点，而不是数组。

示例 1

示例 2

示例 3

示例 4

约束

• 树中节点数在 [0,100] 内。
• -100 ≤ Node.val ≤ 100。

暴力/直觉：递归直接按“左→根→右”遍历，正确且简短；局限是依赖系统调用栈，不容易在第 k 个节点处暂停，也不便展示递归栈现场。

正解 · 显式栈：
① 核心规律：当前节点非空时不断压入左链；左链到底后弹出栈顶访问，再转向它的右子树。栈顶始终是“左子树已完成、自己尚未访问”的最近祖先。
② 样例落地：在根 4 的非对称 7 节点树中，先压 4→2→1，依次访问 1、2；转入 2 的右子 3 后，再回到 4，随后处理右子树，核心动作会重复多轮。
③ 优化取舍：递归和迭代都是 O(n) 时间、O(h) 空间；迭代能随时暂停，LC230 可在弹到第 k 个节点时直接返回，因此面试更值得掌握。

非对称 7 节点树
              4
            /   \
           2     6
          / \   /
         1   3 5
                \
                 7
中序目标：[1,2,3,4,5,7,6]

里程碑1｜从根压左链到底
cur=∅，stack=[4,2,1]，result=[]

里程碑2｜完成左子树 2
依次弹 1、2；转入 2.right=3 后再弹 3
cur=∅，stack=[4]，result=[1,2,3]

里程碑3｜访问根并进入右子树
弹 4；从 6 向左压到 5
cur=∅，stack=[6,5]，result=[1,2,3,4]

里程碑4｜处理 5 的右分支
弹 5 后转入 7，再压入并弹出 7
cur=∅，stack=[6]，result=[1,2,3,4,5,7]

里程碑5｜弹出最后祖先 6
cur=∅，stack=[]，result=[1,2,3,4,5,7,6]

class Solution:
    def inorderTraversal(self, root):
        # 1. 显式保存祖先链、当前指针与访问结果
        result = []
        stack = []
        current = root

        # 2. 先压完整左链，再弹栈访问并转向右子树
        while current or stack:
            while current:
                stack.append(current)
                current = current.left

            current = stack.pop()
            result.append(current.val)
            current = current.right

        return result

# 解法二：递归中序，调用栈隐式保存祖先链
class Solution:
    def inorderTraversal(self, root):
        result = []

        def inorder(node):
            # 1. 空节点不产生访问结果
            if not node:
                return

            # 2. 严格按左子树、当前节点、右子树访问
            inorder(node.left)
            result.append(node.val)
            inorder(node.right)

        inorder(root)
        return result

时间 O(n)，每个节点进出栈各一次；空间 O(h)，h 为树高，栈最多存一条从根到最左的路径(最坏退化链 O(n))。

功能：[1,null,2,3]→[1,3,2]；边界：空树 []→[]、单节点 [1]→[1]；特殊：左斜链/右斜链验证栈的伸缩，BST 输入应输出升序。

考察遍历本质与迭代模拟递归。关联：↔ LC98 验证BST↔ LC230 BST第K小(都利用中序升序)、↔ LC105 前序中序建树。

要完成的任务

给定二叉树根节点 root，返回最大深度，即从根节点到最远叶子节点的最长路径所包含的节点数；空树深度为 0。

输入表示

层序数组只是页面对树的展示，null 表示缺少孩子；函数实际接收根节点。

示例 1

示例 2

约束

• 树中节点数在 [0,10⁴] 内。
• -100 ≤ Node.val ≤ 100。

暴力/直觉：可以 BFS 一层层计数，直到队列为空；它能得到每层节点，但若只求深度，会维护不必要的整层队列。

正解 · 后序求高度：
① 核心规律：depth(node)=1+max(depth(left), depth(right))，空节点返回 0。当前节点必须先拿到左右高度，因此天然是后序。
② 样例落地：示例中叶子 9、15、7 都返回 1；节点 20 收到 1/1 后返回 2；根 3 收到 1/2 后返回 3，公式在叶、内部节点、根连续应用。
③ 优化取舍：递归只保留一条根到当前节点的调用链，空间 O(h)；BFS 空间 O(w)，适合还要读取每层内容的题。高度骨架可直接扩展到 LC543、LC124。

初始树
          3
        /   \
       9     20
            / \
           15  7

帧1｜空孩子先返回 0，三个叶子稳定为高度 1
       9[h=1]       15[h=1]   7[h=1]

帧2｜节点 20 收到 l=1、r=1
          20[h=2]
          /    \
      15[h=1]  7[h=1]

帧3｜根 3 收到左高 1、右高 2
          3[h=3]
        /        \
    9[h=1]      20[h=2]
                 /   \
            15[h=1] 7[h=1]

最终最深路径为 3→20→15（或 7），节点数深度 = 3。

class Solution:
    def maxDepth(self, root):
        def depth(node):
            # 1. 空子树高度为 0
            if not node:
                return 0

            # 2. 后序取得两侧高度，再加上当前层
            left_depth = depth(node.left)
            right_depth = depth(node.right)
            return 1 + max(left_depth, right_depth)

        return depth(root)

时间 O(n)，每节点访问一次；空间 O(h)，递归栈深度等于树高(最坏退化链 O(n))。

功能：[3,9,20,null,null,15,7]→3；边界：空树→0、单节点→1；特殊：完全左斜链 n 个节点→深度 n。

考察后序递归与"自底向上返回值"。关联：↔ LC543 二叉树的直径↔ LC124 最大路径和(都在求高度时顺手更新全局答案)、↔ LC101 对称二叉树。

要完成的任务

给定二叉树根节点 root，对树中每个节点交换左、右孩子，返回翻转后树的根节点。

输入与输出

函数接收并返回根节点；层序数组只是页面展示树结构，null 表示对应孩子不存在。

示例 1

示例 2

示例 3

约束

• 树中节点数在 [0,100] 内。
• -100 ≤ Node.val ≤ 100。

暴力/直觉：层序遍历每个节点并交换左右孩子也能完成，需要 O(w) 队列；若只是递归定义变换，队列不是必需状态。

正解 · 分治翻转：
① 核心规律：翻转当前树等于“翻转原右子树作为新左子树 + 翻转原左子树作为新右子树”。空节点直接返回空。
② 样例落地：示例先把 2 的子树稳定为 2→(3,1)，再把 7 的子树稳定为 7→(9,6)，最后根 4 接成 4→(7,2)；同一规则重复到内部节点和根。
③ 安全写回：先用局部变量保存两棵递归结果，再依次写 root.left、root.right，可清楚避免覆盖原指针。递归空间 O(h)，迭代版空间 O(w)。

同一编号代表同一个节点；局部变量保存的是引用，不复制节点。

里程碑0｜初始
          4
        /   \
       2     7
      / \   / \
     1   3 6   9

里程碑1｜原左子树稳定翻转完成
          2
        /   \
       3     1

里程碑2｜原右子树稳定翻转完成
          7
        /   \
       9     6

里程碑3｜根写入新左边后的必要瞬时态
inverted_left=节点2，inverted_right=节点7
          4
        ↙   ↘
       7①   7①
节点2仍由 inverted_left 保住，因此没有丢链。

里程碑4｜根写入新右边，整树稳定
          4
        /   \
       7     2
      / \   / \
     9   6 3   1

class Solution:
    def invertTree(self, root):
        def invert(node):
            # 1. 空子树翻转后仍为空
            if not node:
                return None

            # 2. 先得到两棵稳定的翻转结果，避免覆盖原引用
            inverted_left = invert(node.left)
            inverted_right = invert(node.right)

            # 3. 原右结果接到左边，原左结果接到右边
            node.left = inverted_right
            node.right = inverted_left
            return node

        return invert(root)

时间 O(n)，每节点交换一次；空间 O(h)，递归栈深度为树高。

功能：[4,2,7,1,3,6,9]→[4,7,2,9,6,3,1]；边界：空树→空、单节点→自身不变；特殊：只有左孩子的链翻转后变右斜链。

考察递归改树结构与交换的原子性。关联：↔ LC101 对称二叉树(镜像判断 vs 镜像构造)、↔ LC104 最大深度(同款递归骨架)。

要完成的任务

给定二叉树根节点 root，判断它是否关于根节点所在的竖直轴镜像对称，返回布尔值。

输入表示

层序数组用于展示树，null 表示缺少孩子。对称比较的是结构和对应节点值：左子树的左边应匹配右子树的右边，反之亦然。

示例 1

示例 2

约束

• 树中节点数满足 1 ≤ n ≤ 1000。
• -100 ≤ Node.val ≤ 100。

暴力/误区：把左右子树按“同侧”比较，只能判断结构相同；轴对称要求交叉配对，left.left 应与 right.right 比。

正解 · 成对镜像递归：
① 核心规律：mirror(a,b) 先处理“都空 / 仅一个空 / 值不同”，再同时验证外侧 a.left↔b.right 与内侧 a.right↔b.left。
② 样例落地：对称 7 节点树中，2L/2R 值相等；外侧继续配 3L/3R，内侧继续配 4L/4R，两层都通过才返回 True。反例在 ∅/3R 处立即失败。
③ 优化取舍：递归只保留成对调用，空间 O(h)；也可用队列按“外侧一对、内侧一对”入队，空间 O(w)，适合避免递归。