1. 选题逻辑：第九天我为什么还在啃基础题

算法题打卡进行到第9天，老实说最难的不是做题，而是在“今天到底刷什么”上反复纠结。很多人打卡断掉，不是不会做，是每天打开LeetCode就开始刷首页推荐，今天一道图论、明天一道位运算，后天又碰上个DP，结果什么都没吃透。我第八天结束的时候给自己定了条规矩：宁可把一道模板题写三遍，也不贪多求快。所以算法题打卡9这天，我的题单只有一个方向——把平时最容易在面试里遇到的“套路题”重新过一遍。

今天的四道题分别是：搜索插入位置、有序数组的平方、反转链表、二叉树的层序遍历。看起来都很基础，对应的正是大家常说的LeetCode必刷基础算法题那一批。但基础归基础，每一道展开之后都有值得单独拎出来说的点。比如二分查找为什么最后返回的是 left 而不是 right，再比如双指针为什么能把 O(n log n) 的平方排序优化成 O(n)，这些东西不亲手写一遍代码，光看答案解析是记不牢的。

考虑到热词里同时提到了 python算法思维题 和 java常见算法题，我这次刻意用 Java 做了主实现，每个题后面附上 Python 版本对照。不是说哪个语言更好，而是想让你看到：算法题的思路是语言无关的，真正决定你能不能写出来的是你脑子里的模型够不够清晰。

2. 第一题：搜索插入位置，二分查找的一锤定音

1.2 题目到底在问什么

给定一个排序数组和一个目标值，如果数组里存在这个目标值，就返回它的下标；如果不存在，返回它应该被插入的位置。举个例子：

nums = [1, 3, 5, 6] target = 5 -> 返回 2 target = 2 -> 返回 1 target = 7 -> 返回 4 target = 0 -> 返回 0

这道题看着简单，但它其实是二分查找里“找左边界”的经典变体。很多人第一次写会用线性扫描，从前往后找第一个大于等于 target 的位置。这样当然能做出来，但面试官下一句往往是“能不能用 O(log n) 的时间”。到那一刻，你要是还没想清楚二分查找的循环不变量，就会在 left 和 right 的边界条件里绕晕。

2.2 Java 实现与循环不变量的确定

直接贴我这次写的 Java 版本：

public int searchInsert(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return left; }

写二分查找最重要的不是背模板，而是想清楚你的循环不变量是什么。我在这个写法里维护的是：left 左边的元素都严格小于 target，right 右边的元素都大于等于 target。在这个前提下，每次循环判断 nums[mid] 和 target 的关系：

• 如果 nums[mid] < target，说明 mid 位置不可能是答案，而且 mid 左边更不可能是答案，所以直接把 left 挪到 mid + 1。
• 否则，说明 nums[mid] 是大于等于 target 的元素，mid 可能是答案，但不能排除左边还有更小的符合条件的元素，所以把 right 挪到 mid - 1。

循环结束时 left > right，此时 left 指向的就是“第一个大于等于 target 的位置”，也就是题目要求的插入位置。针对上面的例子，target=2 时，left 最终会停在 1，正好是 2 应该插入的位置。

Python 版本几乎一模一样：

def searchInsert(nums: list[int], target: int) -> int: left, right = 0, len(nums) - 1 while left <= right: mid = (left + right) // 2 if nums[mid] < target: left = mid + 1 else: right = mid - 1 return left

2.3 为什么返回值是 left 而不是 right

这是这道题最容易让人卡壳的地方。你去看很多题解，知道要返回 left，但不知道为什么。我当时理解透这一点是在纸上把最后一次循环推了一遍之后。

假设 nums = [1, 3, 5, 6]，target = 4。一开始 left=0，right=3，mid=1，nums[1]=3 < 4，所以 left 变成 2。此时 left=2，right=3，mid=2，nums[2]=5 >= 4，所以 right 变成 1。循环结束，left=2，right=1，而 4 确实应该插在下标 2 的位置。

你会发现，循环结束的时候，right 停留在“最后一个小于 target 的元素”的位置，left 停留在“第一个大于等于 target 的元素”的位置。我们要找的是插入位置，也就是“第一个大于等于 target”的位置，所以答案是 left。如果你非要返回 right，那得到的就是前一个元素的下标，在插入逻辑里就错了。

2.4 二分查找的边界坑位

我这次复习时在几个边界细节上专门做了测试，分享给你：

• mid 的计算用 left + (right - left) / 2，不要写成 (left + right) / 2。虽然 Java 里数组长度不太可能大到溢出，但这是个好习惯，尤其当你在 C++ 里处理很大的边界值时，这一步能直接避免整数溢出。

• while 的条件用 <= 而不是 <。如果用 <，循环结束的条件会不同，最后返回的 left 可能不准。关键在于你的循环不变量是怎么定义的，我建议你固定使用 <= 这个版本，因为它在“空区间”出现的时候，left 正好是目标位置。

• 数组为空的情况：如果 nums.length == 0，循环根本不进入，直接返回 0。这个边界很多初学者会忽略，但实际跑测试用例的时候，它经常是第一个报错的地方。

3. 第二题：有序数组的平方，双指针比排序快在哪

3.1 普通做法和优化做法的分水岭

题目描述很简短：给你一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。比如输入 [-4, -1, 0, 3, 10]，输出 [0, 1, 9, 16, 100]。

最直观的做法是先把每个数平方，再对整个数组排序。代码就两行：

int[] res = new int[nums.length]; for (int i = 0; i < nums.length; i++) { res[i] = nums[i] * nums[i]; } Arrays.sort(res); return res;

这个版本的复杂度是 O(n log n)，问题主要出在排序上。但你要是观察一下原始数组的特征，会发现一个很关键的性质：原数组本身就是有序的，只是因为负数平方之后可能变大，导致平方后的数组不再单调。可你有没有注意到，平方之后最大的数一定出现在原数组的两端，不是最左边就是最右边。

这句话就是双指针解法的出发点。既然最大的元素位置可以确定，那我从两端往中间走，每次比较两端谁更大，谁就放到结果数组的最右边，接着缩小范围，结果数组自然就是从前往后递增的。整个过程只需要一次遍历，时间复杂度 O(n)，空间复杂度 O(n)（保存结果数组）。

3.2 双指针代码的完整推导

Java 版我写的是这个：

public int[] sortedSquares(int[] nums) { int n = nums.length; int[] res = new int[n]; int left = 0; int right = n - 1; int index = n - 1; while (left <= right) { int leftSquare = nums[left] * nums[left]; int rightSquare = nums[right] * nums[right]; if (leftSquare > rightSquare) { res[index] = leftSquare; left++; } else { res[index] = rightSquare; right--; } index--; } return res; }

我每次比较的是 nums[left] 的平方和 nums[right] 的平方，谁大谁就放到 res[index] 的位置，然后 index 往左移一格，相当于从结果数组的末尾往前填。因为每次放进去的都是当前剩余部分里最大的平方数，所以整体填下来，res 从后往前是递减的，从前往后看就是递增的。

这里有个小细节值得注意：很多人会倾向于先比较 nums[left] 和 nums[right] 的绝对值，再算平方。功能上没区别，但直接算平方会让代码更直观，特别是有负数的场景下，你不需要额外解释 abs 的意图。你自己选一种固定的习惯就行。

Python 版本：

def sortedSquares(nums: list[int]) -> list[int]: n = len(nums) res = [0] * n left, right, index = 0, n - 1, n - 1 while left <= right: left_sq, right_sq = nums[left] ** 2, nums[right] ** 2 if left_sq > right_sq: res[index] = left_sq left += 1 else: res[index] = right_sq right -= 1 index -= 1 return res

3.3 这个解法背后的思维模型

你在做题的时候一定会遇到“看起来排序能解决，但面试官非要你优化”的场景。这道题就是一个典型。它背后的思维模型是：数组已经有序，哪怕做了一些变换，原有的有序信息也没完全失效，只是需要换一种角度去利用。

所有负数的平方在数组左半段是递减的，所有非负数的平方在右半段是递增的，相当于有两个有序序列，现在要做的就是“合并”这两个序列。双指针从两端往中间走，本质上就是在合并两个有序序列，每次取大的那一个。想通这一点之后，你会发现很多题都能套这个模型。比如后面常见的“合并两个有序数组”、“有序数组去重”、“容器盛水最多的双指针”，都是类似的思想。

3.4 常见翻车点：填充顺序搞反

我第一次自己写这个题的时候，犯过一个不算低级但很容易犯的错误：我用了两个指针从中间往两边走，然后试图从头开始填充 res。结果发现每次选出来的都是局部最小的，最后 res 的前半段顺序是乱的。

正确做法一定是从两端往中间找最大，从后往前填充结果。换句话说，你要找的是当前剩余范围内的“最大值”，而不是“最小值”。如果反过来问“所有平方数里最小的怎么找”，思路其实也成立，但你需要额外处理负数和非负数之间的边界，复杂度会明显增加，完全没有必要。

4. 第三题：反转链表，迭代和递归缺一不可

4.1 为什么这道题是面试高频题

单链表反转几乎是我见到的面试题里出现频率最高的一道。有的公司会把它当成热身题，有的公司会在你写错指针的时候直接结束考察。原因很简单，题目本身不难，但它能一次性考察你对链表结构的理解、对指针操作的熟练度，以及边界条件的处理。

题目描述就一句话：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。比如 1 -> 2 -> 3 -> 4 -> 5，反转后变成 5 -> 4 -> 3 -> 2 -> 1。

如果只在脑子里面想，反转就是把每个节点的 next 指向前一个节点。真动手写代码的时候，你马上会碰到一个问题：当你把当前节点的 next 改掉之后，原来的下一个节点就找不到了。所以你这个操作的顺序必须是：先保存下一个节点，再改当前指针。

4.2 迭代解法：三指针模型

public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode next = curr.next; // 先保存下一个节点 curr.next = prev; // 反转当前节点指针 prev = curr; // prev 前进 curr = next; // curr 前进 } return prev; }

整个过程可以想象成一条链条被一节一节地拆下来，然后重新串到另一个方向。prev 始终指向“已经反转好的那部分链表的头”，curr 指向“当前待处理节点”，next 负责记住“还没处理的原链表剩余部分”。循环结束后，curr 变成了 null，说明所有节点都处理完了，此时 prev 就是新链表的头。

边界情况：head 本身是 null，或者只有一个节点，循环里要么不进入，要么只处理一次，这两种情况都能正确返回，不需要额外写 if。

4.3 递归解法：想清楚子问题返回什么

递归版本是很多人理解起来比较吃力的地方。代码很短：

public ListNode reverseList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode newHead = reverseList(head.next); head.next.next = head; head.next = null; return newHead; }

我自己当初学的时候，最大的困惑是：这代码看起来根本“没有做反转”，就像套了个壳。后来我换了个角度理解，一下子就通了。

当你调用 reverseList(head.next) 时，它返回的是什么？它是“以 head.next 为头节点的那条链表，反转之后的新头节点”。你不需要关心它内部是怎么做到的，你只需要相信这个递归调用能把后面那一整串都反好。反好之后，原来的 head.next 变成了新链表的尾节点，此时让这个尾节点的 next 指向 head，就相当于把 head 接到了反转后链表的末尾。最后再让 head.next = null，把头节点变成新的尾节点，整个链表就反转完了。

这里面最神奇的一行是head.next.next = head。我第一次看到这个写法的时候觉得是绕口令，但确实就是核心。如果你想验证，可以拿 1 -> 2 -> 3 这个三节点链表，在纸上把每一层递归的返回值标出来：reverseList(2) 返回 3 -> 2，然后 2.next.next = 2，也就是 3.next = 2，再把 2.next = null，就得到了 3 -> 2 -> 1。

4.4 面试追问：递归版本的风险

面试时一旦你写出了递归版本，面试官有极大概率会追问一句“这个版本有什么问题”。答案就是：当链表非常长时，递归深度等于链表长度，可能会导致栈溢出。所以实际开发环境里处理长链表，我更推荐迭代版本。面试时如果时间够，我一般会把两种版本都写一遍，然后主动解释它们的取舍，这比等对方面试官来问效果更好。

迭代版本时间 O(n)、空间 O(1)，递归版本时间 O(n)、空间 O(n)（隐式调用栈）。这道题也让我意识到，刷题的时候不要只看“能不能过”，还要主动去思考每种解法在极端场景下的表现。

5. 第四题：二叉树层序遍历，一套模板吃透所有层次遍历

5.1 BFS 标准模板

二叉树层序遍历的题目描述是：给你二叉树的根节点 root，返回其层序遍历结果，每一层的节点值放在一个子列表里。比如：

输入：root = [3, 9, 20, null, null, 15, 7] 输出：[[3], [9, 20], [15, 7]]

这个题的核心就是广度优先搜索（BFS），只不过普通的 BFS 只输出节点值，而层序遍历要求你按“层”把结果分隔开，所以需要额外做一层“分层”处理。Java 代码：

public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if (root == null) { return res; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); List<Integer> level = new ArrayList<>(); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); level.add(node.val); if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } res.add(level); } return res; }

这里面最关键的一行是int size = queue.size();必须在进入 for 循环之前固定下来。如果你把循环条件写成for (int i = 0; i < queue.size(); i++)，queue.size() 在循环过程中会一直变化，因为每次 poll 一个节点之后，又马上 offer 了它的左右孩子，队列的大小并不是固定的，最后各层节点就会混在一起，输出结果完全错乱。

5.2 一个 Python 版本的直观对比

如果你平时写 Python 更顺手，层序遍历用队列也是一样的写法：

from collections import deque def levelOrder(root): res = [] if not root: return res queue = deque([root]) while queue: size = len(queue) level = [] for _ in range(size): node = queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) res.append(level) return res

Python 里len(queue)在 for 循环外就已经固定了，而且 deque 的 popleft() 是 O(1) 操作，比 list.pop(0) 快很多。如果你是做 Python 算法题的，建议直接养成用 deque 的习惯，不要用 list 来模拟队列，否则遇到大数据量测试用例很容易超时。

5.3 同一套代码改三个变形题

层序遍历这个模板吃透了，能直接解决好几道题。我这次打卡顺手把变体也过了一遍，这里列出来给你作为后续练习参考：

• 自底向上层序遍历：最后把 res 反转一下就行，Java 里用 Collections.reverse(res)，Python 里用 res[::-1]，代码其他部分完全不用动。
• 二叉树的右视图：按层遍历时只保留每层的最后一个节点值，也就是内层 for 循环结束后把 node.val 加入结果，而不是把整层列表加入结果。
• 之字形层序遍历：按奇偶层处理。如果当前层是偶数层，正常从左往右；如果是奇数层，把这一层的列表反转之后再加入结果集。很多实现里会直接用双向链表，头部插入尾部插入来回切换，但我觉得先正常 BFS 再单独处理反转，理解起来更容易，代码也更好读。

这道题给我最大的启发是：算法模板不是背下来的，而是通过一道题练熟之后自然迁移的。层序遍历的模板一旦熟练，后面遇到矩阵的 BFS、图的层级遍历、甚至拓扑排序的队列实现，都会有天然的熟悉感。

6. 踩坑实录：今天翻车的四个细节

今天的四道题都不是第一次写了，但我在重新敲代码的时候还是踩了几个不大不小的坑。这里全部记录下来，建议你刷到同类题的时候先避开。

第六天和第七天打卡的时候，我就栽在“以为会了就不用重新敲”这个心态上。这次我学乖了，每道题先自己写，写完之后再对照题解，重点看那些“我跳过去但其实是关键”的地方。比如二分查找的返回值逻辑，我第无数次提醒自己：循环退出时 left 才是边界位置，right 是补刀的那一个。

如果你也在用类似“算法题打卡”的方式刷题，我强烈建议你留一个笔记文件，把每次踩坑记录成表格。这个动作花不了几分钟，但等到第三周复盘的时候，你会发现自己当初最容易错的地方就那么三四个，早一点记录就能早一点形成肌肉记忆。

7. 打卡第九天之后，我对刷题的几点真实体会

写到这里，想说点跟题目本身无关但跟打卡强相关的东西。

我见过不少朋友信誓旦旦地说要每天刷一道题，结果坚持了不到一周就因为“今天太忙”“题目太难”“没啥效果”放弃了。作为一个已经连续打卡九天的过来人，我的体会是：算法题打卡能不能坚持下去，关键不在于意志力，而在于你每天给它分配的任务量是否足够小。

我给自己定的规则很简单，每天只做 2 到 3 道题，做不到就只做 1 道。如果某道题真的毫无思路，看题解也可以，但看完题解之后，必须关掉答案自己重新敲一遍，隔天再复现一次。这个“隔天复现”的动作，比我当天连做五道题都管用。很多知识当天看着懂了，睡一觉就还回去了，复现才是真正把它变成你自己的东西的唯一路径。

第九天打卡结束的时候，我回头看这几天覆盖的题目，发现它们渐渐连成了一张网。二分查找、双指针、链表反转、层序遍历，表面上是四个互不相干的专题，但底层都在训练同一件事：在处理数组、链表、树这些结构时，你如何用一个简洁的状态模型，在一个清晰的循环或递归里完成任务。这种能力的提升不是立竿见影的，但当你写到第二十道、第三十道的时候，会突然发现看题的速度变快了，思路也不容易乱了。

如果你也想开始自己的打卡计划，建议你先别管“必刷题单”有多长，就按今天这个组合来：一道二分、一道双指针、一道链表、一道二叉树，难度都不高，但覆盖了四个最常见的考察方向。把这一组吃透，再去碰更难的题，你会感觉到明显的不同。