1. 数据结构题目收录系列的第二十二期这次我们聊点真东西做数据结构题目收录这个系列做到第二十二期说实话我自己都有点意外。最开始只是想把平时带人刷题时遇到的一些典型题目整理出来方便复盘没想到一路更下来积累了不少读者的反馈也让我重新审视了很多以前觉得“理所当然”的知识点。这一期我打算换个思路不再单纯罗列题目和答案而是围绕几道有代表性的题目把背后的设计思路、常见误区、以及实际编码中容易踩的坑掰开揉碎讲清楚。如果你正在准备技术面试、正在补数据结构的基础、或者单纯想找一些高质量的练习题来打磨编码手感这一期的内容应该都能给你一些参考。题目本身覆盖了线性表、树、图、排序与查找这几个核心板块难度从基础到中等偏上都有我会尽量把每道题的“为什么这么做”讲透而不是只给一个能跑通的代码就完事。这一期的关键词我提炼了几个数据结构题目收录、算法题解析、刷题经验、代码实操、避坑指南。全文会围绕这些关键词展开但不会为了堆砌而堆砌每一段都是我觉得值得展开讲的内容。2. 本期题目整体设计与选题思路2.1 为什么选这些题而不是那些题做题目收录到第二十二期选题其实是最头疼的环节。太简单的题没有讲解价值太偏的题又脱离实际应用场景。我这一期的选题标准有三个第一题目本身要能体现某个数据结构的核心特性比如栈的“后进先出”、树的“递归结构”、图的“遍历策略”第二题目要有一定的变形空间能让我在讲解时顺带延伸到相关的知识点第三题目在实际面试或工程场景中出现频率较高不是那种为了出题而出题的偏题怪题。基于这三个标准本期选了六道题分别对应不同的数据结构类型。线性表部分选了一道关于链表环检测的经典题树部分选了一道二叉搜索树验证的题目图部分选了一道拓扑排序的应用题排序与查找部分选了两道一道考察快排的partition思想另一道考察二分查找的边界处理。最后还有一道综合题把栈和队列结合起来解决一个实际问题。提示选题时不要只看题目难度更要看题目能否帮你建立知识点之间的联系。一道好题的标准是做完之后你能顺带复习好几个相关概念。2.2 题目难度分布与适用人群本期的六道题如果按难度划分大致是这样的链表环检测和二分查找边界处理属于基础偏上适合刚学完对应数据结构的人练手二叉搜索树验证和快排partition属于中等难度适合有一定刷题经验、想巩固递归和分治思想的人拓扑排序应用题和栈队列综合题属于中等偏上适合准备面试、想提升综合运用能力的人。我特意没有选那种需要复杂数学推导或者高级算法技巧的题目因为这一期的定位是“夯实基础、打通思路”而不是“炫技”。如果你能把这几道题背后的原理讲清楚并且能独立写出没有bug的代码那说明你对这些基础数据结构的理解已经比较扎实了。2.3 题目收录系列的长期价值在哪里有人可能会问数据结构题目收录做这么多期到底有什么意义网上随便一搜就有成千上万的题解为什么还要看你的这个问题我自己也想过。后来我想明白了题目收录的价值不在于题目本身有多新而在于讲解的角度和深度。同一道题不同的人写出来的题解质量差别很大。有的人只给代码有的人会讲思路但很少有人会把“为什么这么想”“为什么不能那么做”“实际写的时候哪里容易错”讲清楚。我这个系列一直在尝试做的就是补上后面这部分。每道题我都会先讲清楚它的核心考点是什么然后分析几种可能的解法对比它们的优劣最后给出我推荐的实现方式并附上我在实际编码中踩过的坑。这种“从思路到代码到避坑”的完整链条才是我觉得对读者最有价值的地方。3. 核心题目细节解析与实操要点3.1 链表环检测快慢指针为什么能相遇链表环检测这道题题目描述很简单给定一个链表判断它是否有环。如果单纯用哈希表记录访问过的节点那这道题就没什么好讲的了空间复杂度O(n)思路直白。但面试官通常不会满足于此他们会追问能不能用O(1)的空间复杂度解决这时候快慢指针就登场了。快慢指针的核心思想是设置两个指针一个每次走一步一个每次走两步。如果链表没有环快指针会先到达末尾如果有环快指针会在环内追上慢指针。这个思路听起来简单但很多人第一次接触时会有一个疑问为什么快指针一定会追上慢指针而不是刚好跳过去这就涉及到数学上的追及问题了。假设环的长度为L当慢指针进入环时快指针已经在环内走了k步。由于快指针速度是慢指针的两倍每经过一次移动快指针相对于慢指针就多走一步。所以快指针追上慢指针所需的时间取决于它们之间的初始距离。因为快指针每次相对慢指针靠近一步所以无论初始距离是多少最终一定会追上不会出现“跳过去”的情况。注意快指针每次走两步是经过验证的最优选择。如果快指针每次走三步或更多虽然也能检测到环但在某些环长度下可能会增加相遇的时间而且代码的边界处理会更复杂。实际编码时有几个细节需要特别注意。第一循环条件应该是fast ! null fast.next ! null而不是只判断fast ! null因为快指针每次要走两步必须确保fast.next也存在。第二初始时慢指针指向head快指针指向head而不是head.next这样可以统一处理从第一个节点就开始成环的情况。第三返回结果时如果快指针遇到null说明没有环直接返回false。public boolean hasCycle(ListNode head) { if (head null || head.next null) return false; ListNode slow head; ListNode fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) return true; } return false; }这段代码看起来很短但每一行都有讲究。比如开头的边界判断如果链表为空或只有一个节点直接返回false省去了后续的循环开销。再比如slow fast的判断放在指针移动之后而不是之前这是因为初始时两个指针都指向head如果先判断就会误判为有环。3.2 二叉搜索树验证中序遍历与上下界约束验证二叉搜索树这道题表面上看很简单只要每个节点的左子节点小于它右子节点大于它不就行了吗但如果你真的这么写就会掉进一个经典的陷阱。考虑这样一个树根节点是10左子节点是5右子节点是15然后5的右子节点是12。按照“左小于根、右大于根”的局部判断12大于5看起来没问题但12实际上大于根节点10违反了二叉搜索树的全局性质。所以正确的做法有两种一种是利用中序遍历的有序性另一种是递归时传递上下界。中序遍历的思路很直观二叉搜索树的中序遍历结果一定是严格递增的。所以我们可以中序遍历整棵树检查每个节点的值是否大于前一个节点的值。如果发现逆序就说明不是二叉搜索树。private TreeNode prev null; public boolean isValidBST(TreeNode root) { if (root null) return true; if (!isValidBST(root.left)) return false; if (prev ! null prev.val root.val) return false; prev root; return isValidBST(root.right); }这段代码用了一个全局变量prev来记录中序遍历的前一个节点。注意这里用的是而不是因为二叉搜索树通常不允许重复值。如果题目允许重复值那就需要根据具体定义来调整。另一种上下界的方法更通用一些也更容易理解。递归时给每个节点传递一个允许的取值范围根节点的范围是负无穷到正无穷左子节点的范围是父节点的下界到父节点的值右子节点的范围是父节点的值到父节点的上界。public boolean isValidBST(TreeNode root) { return validate(root, null, null); } private boolean validate(TreeNode node, Integer low, Integer high) { if (node null) return true; if (low ! null node.val low) return false; if (high ! null node.val high) return false; return validate(node.left, low, node.val) validate(node.right, node.val, high); }提示用Integer而不是int来传递上下界是为了处理节点值为Integer.MIN_VALUE或MAX_VALUE的边界情况。如果直接用int初始的上下界就没法表示“无穷”了。3.3 拓扑排序从课程表问题看有向无环图拓扑排序这道题我选的是课程表问题的变体给定一些课程和它们之间的先修关系判断是否可能完成所有课程。这道题的本质是判断一个有向图是否有环。如果有环说明存在循环依赖无法完成如果没有环就可以得到一个合法的学习顺序。拓扑排序有两种经典实现一种是基于BFS的Kahn算法另一种是基于DFS的深度优先搜索。Kahn算法的思路是先统计每个节点的入度然后把所有入度为0的节点加入队列依次取出队列中的节点将它指向的节点的入度减1如果某个节点的入度变为0就加入队列。最后如果处理的节点数等于总节点数说明没有环。public boolean canFinish(int numCourses, int[][] prerequisites) { ListListInteger graph new ArrayList(); int[] indegree new int[numCourses]; for (int i 0; i numCourses; i) { graph.add(new ArrayList()); } for (int[] pre : prerequisites) { graph.get(pre[1]).add(pre[0]); indegree[pre[0]]; } QueueInteger queue new LinkedList(); for (int i 0; i numCourses; i) { if (indegree[i] 0) queue.offer(i); } int count 0; while (!queue.isEmpty()) { int course queue.poll(); count; for (int next : graph.get(course)) { indegree[next]--; if (indegree[next] 0) queue.offer(next); } } return count numCourses; }这段代码的关键在于图的构建和入度的维护。注意prerequisites数组中pre[1]是先修课程pre[0]是后续课程所以边的方向是从pre[1]指向pre[0]。这个方向不能搞反否则入度的统计就全错了。DFS的实现方式稍微复杂一些需要用三种状态来标记节点未访问、正在访问、已访问。如果在DFS过程中遇到了“正在访问”的节点说明存在环。这种实现方式在检测环的同时还能输出具体的环路径适合需要调试的场景。3.4 快速排序的partition边界处理是魔鬼快速排序的partition操作可以说是排序算法里最容易写错的几行代码之一。我见过太多人面试时信心满满地写下快排结果在边界条件上翻车。partition的核心目标是选定一个基准值把数组分成两部分左边都小于等于基准值右边都大于基准值然后返回基准值的最终位置。最经典的Lomuto partition方案是这样的private int partition(int[] arr, int low, int high) { int pivot arr[high]; int i low; for (int j low; j high; j) { if (arr[j] pivot) { swap(arr, i, j); i; } } swap(arr, i, high); return i; }这段代码的逻辑是用i来维护“小于等于基准值的区域”的右边界遍历过程中如果发现小于等于基准值的元素就把它交换到i的位置然后i右移。最后把基准值交换到i的位置此时i就是基准值的最终位置。注意i的初始值是low而不是low1。如果写成low1当数组中所有元素都大于基准值时i会停在low1导致基准值被交换到错误的位置。另一个容易出错的地方是循环条件j high而不是j high。因为arr[high]是基准值不应该参与比较和交换。如果写成j high基准值会被自己和自己比较虽然不会导致错误但逻辑上是不对的。还有一种Hoare partition方案用两个指针从两端向中间靠拢效率略高一些但边界处理更复杂。对于大多数场景Lomuto方案已经足够而且更容易理解和调试。我的建议是除非有明确的性能要求否则优先选择Lomuto方案。3.5 二分查找的边界left、right和mid的三角关系二分查找看起来简单但写出一个完全正确的二分查找并不容易。最大的坑在于边界条件的处理while循环的条件是left right还是left rightmid的计算是(left right) / 2还是(left right 1) / 2right的更新是mid - 1还是mid这些问题的答案取决于你要解决的是哪种类型的二分查找。如果是标准的“查找一个目标值是否存在”那么用left right和mid - 1、mid 1是比较直观的。public int binarySearch(int[] arr, int target) { int left 0, right arr.length - 1; while (left right) { int mid left (right - left) / 2; if (arr[mid] target) return mid; else if (arr[mid] target) left mid 1; else right mid - 1; } return -1; }注意mid的计算用的是left (right - left) / 2而不是(left right) / 2。这是为了防止left right溢出。虽然Java中int溢出的情况比较少见但在处理大规模数据时这个细节很重要。如果是“查找第一个大于等于目标值的位置”或者“查找最后一个小于等于目标值的位置”就需要用left right的循环条件并且right的更新可能是mid而不是mid - 1。这类二分查找的模板我建议单独记忆因为在实际面试中出现的频率很高。提示二分查找的变体很多但核心思想只有一个每次排除一半的搜索空间。只要你能清楚地定义“搜索空间”是什么以及“排除”的条件是什么就能推导出正确的边界处理方式而不需要死记硬背模板。3.6 栈与队列综合用两个栈实现队列最后一道综合题是用两个栈实现一个队列。这道题考察的是对栈和队列特性的理解栈是后进先出队列是先进先出。用两个栈来模拟队列关键在于把一个栈的输出顺序反转过来。具体做法是维护两个栈一个叫inStack一个叫outStack。入队时直接把元素压入inStack。出队时如果outStack不为空直接从outStack弹出如果outStack为空就把inStack中的所有元素依次弹出并压入outStack然后再从outStack弹出。class MyQueue { private StackInteger inStack; private StackInteger outStack; public MyQueue() { inStack new Stack(); outStack new Stack(); } public void push(int x) { inStack.push(x); } public int pop() { if (outStack.isEmpty()) { while (!inStack.isEmpty()) { outStack.push(inStack.pop()); } } return outStack.pop(); } public int peek() { if (outStack.isEmpty()) { while (!inStack.isEmpty()) { outStack.push(inStack.pop()); } } return outStack.peek(); } public boolean empty() { return inStack.isEmpty() outStack.isEmpty(); } }这段代码的关键在于outStack的“懒加载”策略只有当outStack为空时才把inStack的元素转移过去。这样可以保证每个元素最多被转移一次均摊时间复杂度是O(1)。如果每次出队都转移时间复杂度就会退化到O(n)。注意peek操作和pop操作共享了转移逻辑但peek不需要弹出元素所以最后用的是outStack.peek()而不是outStack.pop()。这个细节虽然小但在面试中很容易被忽略。4. 实操过程中容易踩的坑与排查技巧4.1 链表题目的空指针陷阱链表相关的题目空指针异常是最常见的错误来源。以环检测为例如果循环条件只写了fast ! null而没有检查fast.next ! null那么当fast指向最后一个节点时fast.next.next就会抛出空指针异常。这个错误在本地测试时可能不会触发因为测试用例的链表长度可能刚好避开了这个边界但在面试的隐藏测试用例中很容易暴露。排查这类问题的技巧是在写链表代码时先画出链表的边界情况比如空链表、只有一个节点、只有两个节点、有环且环在头部、有环且环在尾部。然后针对每种情况手动模拟代码的执行过程看看有没有访问null的情况。这个习惯看起来笨但能帮你省下大量调试时间。另一个常见的坑是链表的断链问题。在反转链表、删除节点等操作中如果不小心丢失了后续节点的引用就会导致链表断裂。解决方法是在修改指针之前先用临时变量保存后续节点的引用。这个原则在几乎所有链表操作中都适用。4.2 递归题目的栈溢出与重复计算树相关的题目大多可以用递归解决但递归有两个常见的坑栈溢出和重复计算。栈溢出通常发生在树的高度很大时比如一棵退化成链表的树递归深度可能达到节点数。如果节点数超过几万就可能触发栈溢出。解决方法是改用迭代方式或者手动用栈来模拟递归。重复计算是另一个问题。比如在验证二叉搜索树时如果对每个节点都重新计算它的上下界就会导致大量重复工作。正确的做法是在递归过程中传递上下界而不是在每个节点重新计算。这个思路在动态规划中也很常见叫做“记忆化搜索”。提示写递归代码时先确定三件事递归的终止条件是什么、当前层需要做什么、递归的返回值是什么。把这三件事想清楚代码就不容易写错。4.3 图论题目的节点编号与边界图论题目的坑主要集中在节点编号和边界处理上。以拓扑排序为例如果课程编号是从1开始的而数组下标是从0开始的就需要做偏移转换。如果忘记转换就会导致数组越界或者结果错误。这个错误在面试中很常见因为面试官往往不会明确告诉你编号是从0还是从1开始。另一个坑是图的连通性问题。有些图论题目假设图是连通的但实际上可能存在多个连通分量。如果代码只从一个节点开始遍历就会漏掉其他连通分量。解决方法是在外层加一个循环遍历所有节点对每个未访问的节点都启动一次遍历。排查这类问题的技巧是先手动构造几个边界测试用例比如空图、只有一个节点的图、有多个连通分量的图、有自环的图。然后观察代码在这些用例下的表现。如果代码能正确处理这些边界情况那基本就没有大问题了。4.4 排序与查找的稳定性与溢出排序算法的稳定性是一个容易被忽略的点。快速排序是不稳定的因为partition过程中会交换不相邻的元素。如果题目要求稳定排序就需要用归并排序或者插入排序。这个细节在面试中经常被问到但很多人只关注时间复杂度忽略了稳定性。二分查找的溢出问题前面已经提过了这里再强调一下mid left (right - left) / 2是标准写法不要图省事写成(left right) / 2。虽然Java中int溢出的概率不高但这是一个体现基本功的细节面试官很可能会注意到。另一个容易出错的地方是二分查找的循环终止条件。如果写成left right那么当left right时循环会退出此时需要额外判断arr[left]是否等于目标值。如果写成left right循环会在left right时退出此时不需要额外判断。两种写法都可以但必须保持一致不能混用。4.5 常见问题速查表问题现象可能原因排查方法解决方案空指针异常链表访问了null节点检查循环条件是否包含next增加fast.next ! null判断栈溢出递归深度过大打印递归深度或改用迭代改用迭代或手动模拟栈结果错误节点编号偏移错误检查数组下标与节点编号的对应关系统一编号规则或做偏移转换超时重复计算或时间复杂度高分析算法的时间复杂度使用记忆化或优化算法死循环循环条件或指针更新错误打印循环变量检查循环条件和指针更新逻辑数组越界边界条件处理不当检查数组访问的下标范围增加边界判断或调整下标这张表是我在实际刷题和带人过程中总结出来的覆盖了大部分常见问题。遇到bug时可以先对照这张表快速定位问题类型然后再深入排查。5. 从题目到能力如何把刷题转化为真正的数据结构功底5.1 不要只追求AC要追求讲清楚很多人刷题的目标就是“AC”Accepted只要代码能通过测试就万事大吉。但如果你真的想提升数据结构功底就不能只满足于AC。每做完一道题你应该问自己几个问题这道题的核心考点是什么我的解法时间复杂度是多少有没有更优的解法如果面试官追问我能讲清楚每一步的理由吗我见过很多人题目做过了代码也AC了但过了一周再让他做他又不会了。原因就在于他只是记住了代码而没有理解背后的思路。真正掌握一道题的标准是你能在不看题解的情况下从头推导出解法并且能向别人解释清楚为什么这么做。5.2 建立自己的题目分类体系刷题到一定数量后你会发现很多题目其实是同一类问题的变体。比如链表环检测、寻找链表中间节点、判断两个链表是否相交这些题目都可以用快慢指针解决。如果你能把这些题目归为一类总结出它们的共同点和差异点那你的刷题效率会大幅提升。我的建议是每做完一道题就在笔记里给它打上标签比如“快慢指针”“递归”“动态规划”“二分查找”。过一段时间后按标签回顾这些题目看看自己是否真的掌握了这一类问题的通用解法。这种分类回顾的方式比盲目刷新题要有效得多。5.3 从题目延伸到实际工程场景数据结构的题目虽然看起来是“学术”的但它们的应用场景其实很广泛。比如拓扑排序在构建系统、任务调度、依赖管理中都有应用二分查找在数据库索引、日志检索中也很常见栈和队列更是操作系统、网络协议中的基础数据结构。如果你能把题目和实际场景联系起来你对数据结构的理解就会更深一层。比如你在做课程表问题时可以想一想实际的项目管理工具是如何处理任务依赖的如果依赖关系很复杂拓扑排序的性能瓶颈在哪里这种思考方式能帮你把“刷题”转化为“解决实际问题”的能力。5.4 定期复盘比盲目刷题更重要我自己的经验是刷题的数量不是关键关键是刷题的质量和复盘的质量。我每周会花半天时间把这一周做过的题目重新看一遍重点看那些当时做错或者做得很吃力的题目。我会重新写一遍代码然后对比之前的解法看看有没有改进的空间。复盘的时候我还会问自己这道题如果换一个条件解法会怎么变比如把“判断是否有环”改成“找到环的入口”把“验证二叉搜索树”改成“修复二叉搜索树”解法需要做哪些调整这种“一题多变”的练习方式能帮你真正吃透一个知识点而不是只会做某一道具体的题。6. 一些个人体会和后续计划做数据结构题目收录这个系列对我自己来说也是一个不断学习的过程。每次整理题目、写解析、补充避坑经验都会让我重新审视一些以前觉得“已经懂了”的知识点。很多时候写着写着就发现自己其实并没有完全理解某个细节然后就得回去查资料、做实验直到彻底搞明白为止。这一期的六道题我觉得最有价值的不是代码本身而是那些“为什么这么做”和“为什么不能那么做”的分析。代码是可以抄的但思路和判断力是抄不来的。如果你能把这几道题背后的思路内化成自己的东西那以后遇到类似的题目你就能自己推导出解法而不是依赖题解。后续我打算在这个系列里增加一些“一题多解”的内容把同一道题的多种解法放在一起对比分析它们的适用场景和优劣。另外也会尝试加入一些实际工程中的数据结构应用案例让题目和实际场景结合得更紧密。如果你有什么想看的题目类型或者想了解的解题技巧也欢迎告诉我我会尽量在后续的内容里安排上。最后分享一个小技巧如果你在刷题时卡住了不要急着看题解。先给自己15分钟尝试不同的思路哪怕最后没做出来这个思考的过程也会让你在看题解时收获更大。因为你知道自己卡在哪里了题解中的关键点就会格外醒目。这个习惯我坚持了很多年觉得对提升解题能力特别有帮助。