计算机机试里的查找、贪心和链表这三块内容，看起来是三个独立的知识点，实际上在真实的笔试和机试场景里，它们经常纠缠在一起出现。我当年第一次系统刷这类题目的时候，最大的感受就是：单看每一个知识点都不难，难的是在有限时间内判断出这道题到底该用哪种思路，以及怎么在考场上把代码写得又快又不出错。这篇内容就是围绕这三个方向，把我在实际练习和复盘过程中积累的思路、模板、踩过的坑，尽可能完整地摊开来讲。不管你是刚开始准备机试、对链表还停留在“知道有指针”的阶段，还是已经刷过一些题但总在边界条件上翻车，下面这些内容应该都能给你一些直接能用的东西。
1. 三个方向为什么值得放在一起练
1.1 机试场景下的真实考察逻辑
很多人复习的时候习惯把知识点拆开，今天专门练查找，明天专门练贪心，后天再看链表。这种拆法在打基础阶段没问题，但到了机试考场上，题目不会告诉你“这是一道贪心题”。它只会给你一段描述，让你自己判断。而查找、贪心、链表这三类问题之所以值得放在一起对照着练，是因为它们分别对应了机试中最常见的三种思维模式：查找考的是“如何在数据里快速定位”，贪心考的是“如何做局部最优决策”，链表考的是“如何在不连续的内存上维护结构”。
我见过不少同学，单独做二分查找的题正确率很高，但一到“在旋转数组里找最小值”这种变体就卡住；贪心题单独看能理解，但题目稍微换个包装就认不出来该用贪心；链表的基本操作会写，但一涉及删除倒数第几个节点、判断环的入口这类问题就开始画图画出错。这些问题的根源不在于知识点没学过，而在于没有建立起“题型特征到解题策略”的快速映射。把这三块放在一起练，本质上是在训练这种映射能力。
从考察频率来看，这三类内容在机试中的占比相当稳定。查找类问题几乎每套卷子都会出现，形式从最简单的顺序查找、二分查找，到稍复杂的哈希映射、区间查找都有；贪心类问题往往以“最优安排”“最少操作”“最大收益”的面貌出现，题干里经常藏着排序这个前置步骤；链表类问题则更偏向对指针操作和边界处理的考察，题目本身不长，但写错一个 next 指针就可能全盘皆输。
1.2 三类问题的共性：边界处理决定成败
我在复盘自己做错的题目时发现一个规律：这三类问题里，真正因为“思路完全不会”而丢分的比例其实不高，大部分失分都集中在边界条件处理上。二分查找的 while 循环到底是 left < right 还是 left <= right，mid 要不要加一，这些细节错一次就会错一片；贪心问题里排序的稳定性、相等元素的处理顺序，往往决定了结果对不对；链表问题里头节点、尾节点、空链表这三种情况，几乎每次都要单独考虑。
所以我在练习的时候养成了一个习惯：每写完一道题，不管通没通过，都先把边界情况列一遍，空输入、单元素、全部相同、首尾特殊，逐个在脑子里过一遍。这个习惯看起来笨，但实测下来能挡掉相当一部分低级错误。下面几个章节里，我会把每一类问题的边界清单都整理出来，你可以直接拿去对照。
2. 查找问题：从顺序扫描到二分收缩
2.1 查找问题的题型识别与策略选择
拿到一道查找题，第一步不是急着写代码，而是先判断数据有没有序、需不需要多次查询、数据规模大概在什么量级。这三个判断直接决定了你该用哪种查找方式。如果数据是无序的、而且只查一次，那顺序扫描就是最合理的选择，没必要为了“看起来高级”去排序再二分，排序本身的开销可能比扫描还大。如果数据有序，或者可以承受排序的开销、并且需要多次查询，那二分查找就是首选。如果查询的关键字是离散的、且范围可控，用哈希表做映射往往能把单次查询降到常数级别。
我整理了一个简单的判断表，实际做题时按这个顺序过一遍，基本不会选错策略：
| 数据特征 | 查询次数 | 推荐策略 | 时间复杂度 |
|---|---|---|---|
| 无序、规模小 | 单次或少量 | 顺序扫描 | O(n) |
| 有序或可排序 | 多次 | 二分查找 | O(log n) 每次 |
| 关键字离散可控 | 多次 | 哈希映射 | O(1) 平均 |
| 需要区间统计 | 多次 | 前缀和或树状结构 | 视结构而定 |
这里要特别提醒一点：二分查找的前提是有序，但有序不等于一定要排序。有些题目给的数据本身就有隐含的单调性，比如“旋转有序数组”“山脉数组”这类，虽然整体不是严格升序，但局部满足二分的收缩条件，这时候直接用二分反而比先排序更高效。识别这种隐含单调性，是查找类题目拉开差距的地方。
2.2 二分查找的三种模板与选择依据
二分查找看起来简单，但真正写起来，区间开闭、循环条件、更新方式这三个变量一组合，能变出好几种写法。我在练习中固定使用三套模板，分别对应三种不同的查询目标，这样考场上不用临时推导，直接套用再微调即可。
第一套是查找目标值是否存在，也就是最经典的二分。区间用左闭右闭[left, right]，循环条件是left <= right，中点计算用mid = left + (right - left) / 2避免溢出，找到就返回，找不到根据大小收缩区间。这套模板的关键在于循环结束时left > right，所有元素都被排除。
第二套是查找第一个大于等于目标值的位置，也就是常说的下界。这套模板的区间习惯用左闭右开[left, right)，循环条件是left < right，中点不需要加一，最终left就是答案。这套写法在处理“插入位置”“第一个满足条件的元素”这类问题时特别顺手，因为不需要在循环里做额外的判断。
第三套是查找最后一个小于等于目标值的位置，也就是上界。这套模板的中点计算需要加一，即mid = left + (right - left + 1) / 2，否则在只剩两个元素时可能死循环。这个加一是很多人容易漏掉的细节，我当初就在这里卡了很久，后来养成习惯，只要看到“找最后一个”就条件反射地加一。
# 模板一：查找目标值是否存在 def binary_search(nums, target): left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return -1 # 模板二：查找第一个 >= target 的位置（下界） def lower_bound(nums, target): left, right = 0, len(nums) while left < right: mid = left + (right - left) // 2 if nums[mid] < target: left = mid + 1 else: right = mid return left # 模板三：查找最后一个 <= target 的位置（上界） def upper_bound(nums, target): left, right = 0, len(nums) - 1 while left < right: mid = left + (right - left + 1) // 2 if nums[mid] <= target: left = mid else: right = mid - 1 return left提示：三套模板不要混用。混用最典型的后果就是死循环或者漏掉边界元素。我的建议是每套模板都练到能默写，然后在做题时先判断属于哪一类，再选模板，而不是每次从零推导。
2.3 哈希查找的适用边界与实现细节
哈希查找在机试里的出场率比二分低一些，但一旦用对场景，代码量和运行效率都很有优势。它最适合的场景是：需要频繁查询某个值是否出现过、或者某个值出现了几次。比如“两数之和”“第一个只出现一次的字符”“统计频次”这类问题，用哈希表往往几行代码就能解决。
实现上有两个细节值得注意。第一是键的选择，如果数据范围不大且是整数，直接用数组当哈希表比用字典更快，因为省掉了哈希计算和冲突处理的开销。比如统计小写字母出现次数，开一个长度 26 的数组就够了。第二是查询与插入的顺序，在“两数之和”这类问题里，必须先查询再插入，否则同一个元素可能被自己匹配到，导致错误答案。这个顺序问题我踩过不止一次，后来养成习惯，凡是涉及“配对”的哈希题，都先想清楚查询和插入的先后。
哈希的局限也很明显：它不维护顺序，所以涉及“第 k 小”“区间内有多少个”这类问题时，哈希就无能为力了，得换用有序结构或者前缀和。判断标准很简单，只要题目问的是“存在性”或“频次”，优先考虑哈希；只要问的是“顺序”或“范围”，就换别的结构。
3. 贪心问题：局部最优如何通向全局最优
3.1 贪心策略的识别信号与验证方法
贪心是三类问题里最“玄”的一个，因为它的正确性不像二分那样有明确的模板保证，很多时候要靠对题目的直觉判断。但直觉是可以训练的，我在大量练习后总结出几个识别信号：题目里出现“最多”“最少”“最大”“最小”这类极值词，且操作之间没有明显的后效性，也就是当前的选择不会让后面的选择变得更差，这时候贪心往往可行。典型例子是区间调度、找零钱（特定面额）、跳跃游戏这类问题。
但光有信号还不够，贪心最大的风险是局部最优不等于全局最优。我验证贪心策略是否正确的办法有两个：一是构造反例，想几个边界数据，看看贪心选择会不会导致后面无解或者结果变差；二是交换论证，假设存在一个最优解和贪心解不同，尝试通过交换元素证明贪心解不会更差。考场上时间紧，通常用构造反例快速验证就够了，如果一时找不到反例，再考虑用动态规划兜底。
这里要强调一个常见误区：不是所有极值问题都能贪心。比如“零钱兑换”在面额是任意值时，贪心就可能出错，必须用动态规划。判断的关键在于贪心选择是否具有“无后效性”，也就是当前选择不影响后续子问题的结构。如果影响，那就不是纯贪心问题。
3.2 排序在贪心中的前置作用
我统计过自己做过的贪心题，超过一半都需要先排序。排序的作用是把问题转化成“按某个顺序依次决策”的形式，从而让贪心选择变得自然。比如区间调度问题，按结束时间排序后，每次选最早结束的区间，就能得到最多不重叠区间数；再比如任务安排问题，按截止时间排序后依次处理，就能判断是否可行。
排序的关键字选择是这类题的核心。选错了关键字，贪心就失效。以区间问题为例，如果目标是“最多不重叠区间”，按结束时间排序；如果目标是“最少箭矢引爆气球”，也是按结束位置排序；但如果目标是“合并区间”，就要按起始位置排序。同样是区间，目标不同，排序关键字就不同。我在做题时会先把目标用一句话写下来，再问自己“按什么顺序处理能让每一步的选择最不容易后悔”，答案往往就是排序关键字。
还有一个细节是相等元素的处理。当排序关键字相同时，次要关键字的选择可能影响结果。比如结束时间相同的区间，起始时间早的应该排前面还是后面，取决于具体问题。稳妥的做法是在排序时把次要关键字也显式写出来，避免依赖排序算法的默认稳定性。
# 区间调度：按结束时间排序，选最多不重叠区间 def max_non_overlap(intervals): if not intervals: return 0 intervals.sort(key=lambda x: (x[1], x[0])) count = 1 end = intervals[0][1] for start, e in intervals[1:]: if start >= end: count += 1 end = e return count3.3 贪心与动态规划的边界判断
很多同学分不清什么时候用贪心、什么时候用动态规划，我的经验是看决策是否影响后续状态。如果每一步的最优选择只依赖当前状态，不依赖之前怎么走到这里的，那贪心可行；如果当前选择会改变后续可选的集合，那就得用动态规划记录状态。
举个具体的对比：跳跃游戏里，每个位置能跳多远是固定的，你只需要维护“当前能到达的最远位置”，每步更新这个值，这是贪心；但如果题目变成“跳到终点有多少种方式”，那就得用动态规划累加方案数，因为不同的跳法会影响后续的计数。这个对比很能说明问题：贪心关心的是“能不能到”，动态规划关心的是“有多少种到法”。
考场上如果拿不准，一个实用的策略是先用贪心写一版，用小数据对拍验证，如果发现反例再改成动态规划。虽然多花一点时间，但比一开始就纠结用哪种方法要高效。
4. 链表问题：指针操作与边界防守
4.1 链表题的通用解题框架
链表题的特点是代码短、逻辑绕、边界多。我在练习中形成了一个固定的解题框架，分四步走：画图、定指针、处理边界、验证。画图不是浪费时间，而是把指针的指向关系可视化，尤其是涉及多个指针同时移动的题目，不画图很容易绕晕。定指针是指明确需要几个指针、各自的作用是什么，比如快慢指针、前驱指针、哑节点。处理边界是指单独考虑空链表、单节点、头节点被删除、尾节点被操作这几种情况。验证是指用一个小例子手动走一遍代码，确认指针移动和终止条件都对。
这个框架里，哑节点是我最常用的技巧。所谓哑节点，就是在头节点前面加一个虚拟节点，让它指向真正的头节点。这样做的好处是，当头节点可能被删除或修改时，不需要单独写一套逻辑，统一用“前驱节点的 next”来处理即可。比如删除链表中的某个值、合并两个有序链表、反转链表的部分区间，用哑节点都能让代码简洁不少。
# 哑节点示例：删除链表中所有值为 val 的节点 class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def remove_elements(head, val): dummy = ListNode(0) dummy.next = head prev = dummy while prev.next: if prev.next.val == val: prev.next = prev.next.next else: prev = prev.next return dummy.next4.2 快慢指针的典型应用场景
快慢指针是链表题里出现频率最高的技巧，没有之一。它的核心思想是让两个指针以不同速度移动，从而在一次遍历中获取位置信息。最常见的三个应用是：找中点、判断环、找环入口。
找中点的做法是快指针每次走两步、慢指针每次走一步，快指针到末尾时慢指针正好在中间。这里有个细节：链表长度是奇数还是偶数，中点的定义会不同。如果要求“中间偏左”，快指针的终止条件要写成fast.next and fast.next.next；如果要求“中间偏右”，条件改成fast and fast.next。这个区别在做“重排链表”“回文链表”这类题时很关键，选错了中点位置，后续逻辑就全错。
判断环的做法是快慢指针同时出发，如果存在环，快指针一定会在环内追上慢指针。找环入口则需要在相遇后，把一个指针放回头节点，然后两个指针同速前进，再次相遇的位置就是入口。这个结论的推导涉及一点数学，但结论本身很好记，我当初是直接背下来的，做题时套用即可。
注意：快慢指针的循环条件一定要先判断
fast再判断fast.next，顺序反了会触发空指针异常。这个错误我在早期练习中犯过好几次，后来养成习惯，写条件时从外到内逐层判断。
4.3 链表反转与局部操作的实现要点
反转链表是链表操作的基本功，迭代和递归两种写法都要会。迭代写法的核心是三个指针：prev、curr、next，每次把curr.next指向prev，然后三个指针整体后移。这里的关键是先保存 next 再改指向，否则改完指向就找不到后面的节点了。递归写法则更简洁，思路是“先反转后面的部分，再把当前节点接到反转后的尾部”，但递归深度受链表长度限制，长链表可能栈溢出，机试里如果链表很长，优先用迭代。
局部反转，也就是反转从位置 m 到 n 的区间，是反转的进阶版。做法是先走到 m 的前一个节点，然后用“头插法”把区间内的节点逐个插到前面。头插法的好处是不需要额外记录区间尾部的后继，每次把当前节点摘下来插到区间头部即可。这个技巧在“两两交换节点”“k 个一组反转”这类题里都能复用。
链表题还有一个容易被忽视的点是修改后的连接。局部操作完成后，一定要检查区间的前驱和后继是否正确连接，尤其是区间在头部或尾部时。我习惯在纸上把操作前后的指针关系画出来，对照代码逐行确认，这个习惯帮我挡掉了不少隐蔽的错误。
5. 三类问题的交叉与综合应用
5.1 查找与贪心的组合题型
有些题目表面上是贪心，但贪心决策的过程中需要频繁查找，这时候查找的效率就决定了整体复杂度。典型场景是“每次选择当前最小的元素”这类问题，如果每次都用线性扫描找最小，整体就是 O(n²)；如果用堆或者有序结构维护，每次取最小就是 O(log n)，整体降到 O(n log n)。机试里数据规模一大，这个差距就是过与不过的区别。
我在做这类题时的判断方法是：先写出贪心策略，再看策略里有没有重复的查找动作。如果有，就考虑用合适的数据结构把查找加速。比如“合并果子”问题，每次取最小的两堆合并，用优先队列实现就比每次排序高效得多。这个思路本质上是用数据结构的查找能力去支撑贪心策略的执行。
5.2 链表与查找的结合场景
链表本身不支持随机访问，所以“在链表中查找”天然就是 O(n) 的。但有些题目会在这个基础上做文章，比如“找出链表中倒数第 k 个节点”，如果用两次遍历，第一次数长度、第二次走到目标位置，是 O(n) 但要走两遍；用快慢指针，快指针先走 k 步，然后两个指针同速前进，快指针到末尾时慢指针就是目标，一遍遍历搞定。这个技巧的本质是用两个指针的相对位置代替长度信息，是一种空间换时间的思路。
还有一类是“有序链表”的查找，虽然不能二分，但可以利用有序性提前终止。比如在有序链表中插入一个节点，找到第一个大于目标值的位置就可以停下，不需要遍历到底。这类题的关键是利用数据本身的顺序信息减少无效访问，和数组二分的思路一脉相承。
5.3 综合题的拆解策略
真正让很多人头疼的是综合题，一道题里同时涉及查找、贪心和链表操作。面对这种题，我的策略是先拆结构、再定策略、最后抠边界。拆结构是指把题目分解成几个独立的子问题，比如“先对链表排序，再在有序链表里做某种贪心选择”；定策略是指为每个子问题选择合适的算法；抠边界是指把子问题之间的衔接处单独检查，因为综合题的错误往往出在衔接上。
拆解的时候建议用注释把每个阶段的目标写清楚，代码分段写，每段写完单独验证。这样即使某一段出错，也能快速定位，不至于整段重写。我在练习综合题时，经常在代码里留这样的分段注释，回头复盘时一目了然。
6. 常见问题与排查技巧实录
6.1 二分查找的死循环与漏解排查
二分查找最常见的问题就是死循环和漏解，两者的根源都在区间更新上。死循环通常发生在“找最后一个满足条件的位置”这类问题上，原因是中点计算没有加一，导致left和right相邻时mid始终等于left，区间无法收缩。解决办法就是前面提到的，找最后一个时中点加一。
漏解则多发生在循环条件写错，比如该用left <= right的地方用了left < right，导致最后一个元素没被检查。排查方法是拿一个长度为 1 的数组手动走一遍，看循环能不能进入、能不能正确返回。这个测试用例虽小，但能暴露大部分循环条件的问题。
| 问题现象 | 常见原因 | 排查方法 |
|---|---|---|
| 程序卡死不结束 | 中点未加一，区间不收缩 | 检查找最后一个时的 mid 计算 |
| 结果差一 | 循环条件开闭写错 | 用单元素数组手动验证 |
| 越界访问 | 中点计算溢出或边界未判 | 改用 left + (right-left)/2 |
| 找不到目标 | 区间更新方向反了 | 对照模板逐行检查 |
6.2 贪心策略失效的识别与补救
贪心失效的表现是“样例过了但提交挂”，或者“小数据对但大数据错”。遇到这种情况，先别急着改代码，而是构造几个针对性强的反例，看看贪心选择在什么情况下会做出错误决策。如果确认贪心不可行，就果断换成动态规划或者暴力搜索加剪枝。
我踩过的一个典型坑是“区间覆盖”类问题，一开始按起始位置排序贪心，结果在某些数据上不是最优，后来改成按结束位置排序才通过。这个教训说明，排序关键字的选择必须和贪心目标严格对应，不能想当然。补救的办法是在纸上把几种排序方式都试一遍，看哪种能构造出反例，反例最少的往往就是正确方向。
6.3 链表指针错误的定位方法
链表题出错，最难受的是不知道错在哪，因为指针一乱，后面的结果全错。我的定位方法是分段打印，在关键操作前后把链表的值打印出来，对比预期。虽然机试环境不一定方便打印，但本地调试时这招非常有效。另一个方法是画图对照，把代码每一步的指针状态画在纸上，和预期状态比对，差异出现的位置就是 bug 所在。
还有一个高频错误是忘记更新尾节点的 next 为 None，导致链表出现环或者多出不该有的节点。这个错误在反转、合并、分割类题目里特别常见。我的习惯是，凡是涉及修改链表尾部的地方，都显式写一行把尾节点的 next 置空，宁可多写一行，也不留隐患。
7. 我在练习中沉淀的几个实用习惯
第一个习惯是每道题都写边界清单。空输入、单元素、全相同、首尾特殊，这四类边界几乎覆盖了大部分出错场景，写完代码先对着清单过一遍，比盲目提交再调试高效得多。第二个习惯是模板默写，二分的三套模板、链表的反转和快慢指针，我都练到能不看资料直接写出来，考场上省下的推导时间可以用来检查边界。第三个习惯是对拍验证，贪心题写完先用小规模随机数据和自己写的暴力解法对拍，确认无误再提交，这个习惯帮我挡掉了不少“样例过但隐藏用例挂”的情况。
这些习惯单独看都不复杂，但坚持下来，做题的稳定性和速度都会有明显提升。机试考的不只是会不会，更是能不能在压力下稳定输出，而这些习惯本质上就是在把“稳定”变成肌肉记忆。
