把面试经典150题刷到第36到第40题这个位置时很多人会明显感觉到一道分水岭——前面还在靠朴素的遍历和暴力思路硬扛到这里开始逼着你用数据结构本身的特性来解题了。这5道题覆盖了栈、链表双指针、快慢指针、滑动窗口、链表模拟加法全是面试里最高频的考点形态而且每道题都能在真实面试中变体成更复杂的版本。这五道题适合谁说实话不只是正在刷题准备面试的人适合哪怕是工作中写了很久业务代码、想补一补基本功的人也很值得花一个下午把它们吃透。因为它们考察的不是“背题型”而是“在约束条件下选择合适数据结构”的能力。我见过不少候选人简历上写着熟悉数据结构结果连“什么时候用栈、什么时候用队列”都讲不清楚。而这几道题恰好能把这些问题全部逼出来。1. 题36有效的括号——栈的经典应用1.1 为什么这个场景必须用栈题目大概是给一个只包含()[]{}的字符串让你判断括号是否匹配。很多人第一次看到这个题会觉得很简单真上手写又会出错问题就出在对“最近匹配”这个特性的理解上。括号匹配的本质是后出现的左括号要被先出现的右括号匹配掉。这种“后进先出”的顺序关系天然就是栈的模型。可以想象成一摞盘子你每次往上面放一个左括号入栈遇到右括号时只能拿最顶上的盘子来比对出栈如果对不上说明整个字符串的括号结构是乱的。这里我建议一个写法上的技巧不要傻乎乎地存左括号而是遇到左括号时把对应的右括号入栈。这样遇到右括号时只需要pop出来比对是否相等即可代码会简洁非常多。1.2 代码实现和边界细节def isValid(s: str) - bool: stack [] mapping {): (, ]: [, }: {} for ch in s: if ch in mapping: if not stack or stack[-1] ! mapping[ch]: return False stack.pop() else: stack.append(ch) return not stack这段代码里最容易被忽略的坑是stack[-1] ! mapping[ch]之前的not stack判断。如果字符串以右括号开头比如)此时栈是空的你直接访问stack[-1]会报错。很多人在面试时挂就挂在这种边界上所以无论什么时候写栈相关的题先想一想“栈空不空”永远是第一步。如果追求极致简洁也可以用入栈右括号的写法再配合if判断。实际写哪种都行关键是能清楚解释每一步是在干什么。面试官更看重的是你能否说清楚“为什么要用栈”而不是代码背得多熟。2. 题37合并两个有序链表——双指针与哨兵节点2.1 迭代写法里的双指针思路两个链表都已经升序排列要求合并后依然有序。这题写起来套路非常固定两个指针分别指向两条链表当前节点哪边小就接哪边然后把该侧的指针向后移一位直到其中一条链表走完最后把剩下那条链表直接接在末尾。这里最重要的问题是合并结果的总共mn个节点需要依次串起来每次“接一个节点”都要知道上一个节点是谁。如果直接在原链表上改来改去代码会绕。所以实际写的时候几乎都会用一个哨兵节点dummy node来占住头位置。2.2 哨兵节点的价值我的经验是只要涉及“把多个节点串成一个新链表”的题目直接 new 一个哑节点永远是最稳的选择。好处在于你不需要单独处理“第一个节点谁来当头”这个问题最后直接返回dummy.next就行。这就像先在地上插一根标杆后面每接一个节点都顺着标杆走完全不用管“第一块砖”怎么放。def mergeTwoLists(l1: ListNode, l2: ListNode) - ListNode: dummy ListNode(0) cur dummy while l1 and l2: if l1.val l2.val: cur.next l1 l1 l1.next else: cur.next l2 l2 l2.next cur cur.next cur.next l1 if l1 else l2 return dummy.next很多人会纠结用递归还是迭代。递归的写法代码更短但如果递归深度太深会有调用栈溢出的风险而且面试时如果要你分析空间复杂度递归版需要O(mn)的栈空间迭代版只要O(1)。所以我个人建议如果你不是专门为了展示递归思路默认写迭代版比较理性。3. 题38环形链表——快慢指针的巧妙应用3.1 快慢指针为什么会相遇判断一个链表有没有环最直观的做法是哈希表遍历每个节点把地址存下来如果遇到重复地址说明有环。这个解法没问题时间复杂度O(n)空间复杂度O(n)。但面试官几乎一定会追问一句“能不能做到常数空间”这时候快慢指针就登场了。慢指针每次走一步快指针每次走两步。如果链表有环两个指针最终一定会在环里相遇。原理可以这样理解两个人在环形操场跑步跑得快的人每圈多跑一段距离最终必然会从后面追上慢的人。你不需要精确证明只要理解“一旦进入环快指针相对慢指针的速度是1步距离会逐渐缩短到0”面试时这一点表达清楚就足够了。def hasCycle(head: ListNode) - bool: slow fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: return True return False这里有个小细节循环条件是fast and fast.next因为快指针一次走两步必须确保它下一步不越界。很多人写成while fast.next碰到只有一个节点的链表也会崩。3.2 如果还要找环的入口经典150题里这题有时会进阶成“返回环的入口节点”。方法是快慢指针第一次相遇后把一个指针移回链表头部然后两个指针都每次走一步再次相遇的地方就是环的入口。这个结论的推导网上有大量资料核心是数学关系从头节点到环入口的距离等于第一次相遇位置继续走到环入口的距离。随便举个例子就能验证但面试时更重要的是你能画出图来推导一遍而不是丢出结论。我之前在模拟面试时候发现很多人能写出代码但被问到“为什么两个指针再次相遇一定在入口”时会卡住。强烈建议把这部分的推导过程自己手动推一遍这套逻辑熟了这类题都能通吃。4. 题39无重复字符的最长子串——滑动窗口的第一次正式亮相4.1 从暴力解到滑动窗口的优化给定一个字符串要求找出不含重复字符的最长子串的长度。暴力做法是枚举所有子串检查里面有没有重复字符时间复杂度能到O(n^2)字符串一长根本扛不住。滑动窗口的基本思路是用两个指针left和right框住一个窗口窗口内保证没有重复字符。每次把right向右扩展一格如果新字符不在窗口内直接扩大窗口如果已经在窗口内就把left收缩到重复字符后面一格。关键在于你怎么快速知道“某个字符在不在窗口里”用一个哈希表记录每个字符最近一次出现的下标即可。4.2 控制窗口收缩的细节def lengthOfLongestSubstring(s: str) - int: last_seen {} left 0 ans 0 for right, ch in enumerate(s): if ch in last_seen and last_seen[ch] left: left last_seen[ch] 1 last_seen[ch] right ans max(ans, right - left 1) return ans注意我特意写了一个条件last_seen[ch] left。这个判断很关键因为哈希表里记录的是这个字符最近一次出现的下标但这个下标可能发生在左指针收缩之前已经不属于当前窗口了。如果不加这个条件你会遇到一种经典的错解——窗口明明已经把重复字符踢出去了左指针还被旧位置往回拽。我见过不少人面试时在这个地方翻车就是因为没搞清楚“哈希表里存的是历史位置不一定是当前窗口内的位置”。理解清楚这一点滑动窗口的门就算真正迈进去了。5. 题40两数相加——链表模拟数字加法5.1 核心难点是进位不是链表题目给出两个逆序存储的链表每个节点存一位数字要求返回一个同样逆序存储的和。为什么要逆序因为链表只能从头部遍历逆序存储刚好能让低位对齐从最低位开始逐位相加和现实里我们做加法竖式的方向一致。这题代码本身不长真正麻烦的是进位处理。每一位相加的结果是v1 v2 carry其中carry是上一位的进位只能是0或1。那么当前位的结果就是sum % 10进位就是sum // 10。def addTwoNumbers(l1: ListNode, l2: ListNode) - ListNode: dummy ListNode(0) cur dummy carry 0 while l1 or l2 or carry: v1 l1.val if l1 else 0 v2 l2.val if l2 else 0 total v1 v2 carry cur.next ListNode(total % 10) carry total // 10 cur cur.next if l1: l1 l1.next if l2: l2 l2.next return dummy.next5.2 最容易漏掉的三种边界情况第一种两条链表长度不一样比如3-4和5-6-7。短的走完就不走了剩下的高位继续和0相加所以代码里用l1.val if l1 else 0处理空指针。第二种最后还有一位进位。比如9-9加1结果是0-0-1链表的长度比原来更长。如果循环条件里漏了or carry最后一个进位节点就不会被创建。第三种有一个链表本身就为空。虽然题目说非空但面试时你要主动提这个边界说“如果输入是空链表怎么兜底”这会给你加分。这题同样适合用哨兵节点来建新链表和合并有序链表的套路一致。刷到这里你会发现链表题的守则在重复出现哨兵节点解决头节点问题、空判断永远放在取值前面、循环条件要把“残留”的情况考虑进去。6. 这五道题串起来的面试方法论6.1 从题36到题40面试官到底在考察什么如果把这五道题放到一起复盘你会发现它们的覆盖面很有层次。题36栈考察的是你对数据结构特性的敏感度题37合并有序链表考察的是链表操作的熟练度和哨兵节点运用题38环形链表考察的是双指针技巧和空间复杂度优化意识题39无重复字符最长子串考察的是从暴力解法到线性解法的优化思维题40两数相加考察的是模拟类题目的边界处理能力。这几项能力合起来基本就是初级/中级算法面试中最核心的考察面。很多时候面试官并不是期待你一次写对而是看你能不能在自己的代码里找到边界漏洞并且说明为什么这样设计是合理的。刷题如果只刷了数量而没总结出这层规律效果会差很多。6.2 我最建议的复盘方式每道题做完之后不要急着看下一道。我之前带过一些人准备面试发现效率高的做法是每做完一题在代码旁边用三行话回答三个问题。第一这题最核心的数据结构/算法技巧是什么。比如题39是“滑动窗口 哈希表”红黑树、堆、并查集这些都算技巧。第二最容易被忽略的边界条件是什么。把五个“坑”收集起来过几天回来只看这些坑就像考前看错题本一样。第三这题能不能变形成其他题。比如题37的哨兵节点在题40里也适用题38的快慢指针在“寻找链表中间节点”里也能用。把题与题之间建立连接才是真正把题刷透。我个人刷到这类题目时习惯把代码在纸上手写一遍再敲到编辑器里。看起来多花时间但练习到的是“边界判断”的肌肉记忆面试时面对白板会更从容。每天保持两到三题这个节奏坚持半个月效果比周末突击五十道强得多。6.3 常见问题速查表题目场景核心技巧最容易踩的坑应对思路括号匹配栈 哈希映射栈空时访问栈顶先判断not stack再取栈顶合并有序链表哨兵节点 双指针头节点处理繁琐永远用dummy.next返回链表判环快慢指针空指针/单节点循环条件用while fast and fast.next最长无重复子串滑动窗口 哈希哈希里存的是历史下标加last_seen[ch] left判断链表示数加法模拟 进位总长超过两条链表循环条件加or carry这份速查表是我自己面试前常翻的东西。到了冲刺阶段如果时间紧张比起重新刷一遍完整代码花二十分钟过一遍这张表反而更容易把状态稳住。最后再分享一个最近实际用到的小发现题36的栈思想在解析 Markdown 或 HTML 标签时同样好使题39的滑动窗口在处理日志里连续时间窗口统计时也经常出现。刷题从来不只是为了应付面试它们会在某一天的某段业务代码里以你意想不到的方式重新出现。这就是为什么我一直觉得认真把这五道题吃透是性价比很高的时间投入。