数据结构面试题以及答案整理这个话题我最近花了大概两周时间重新梳理了一遍。之前在中型技术团队做过几年后端开发也协助部门做过不少轮校招和社招的技术面试坦白说数据结构的题目是最能快速暴露候选人基本功的环节。同一个题有的人十分钟写完还主动讲了优化方案有的人半小时才勉强跑通。今天把常见的高频题、完整的答题思路、以及我实际做面试官时观察到的高频失分点一次性整理出来给正在准备的朋友做个参考。1. 为什么数据结构面试题值得逐题吃透1.1 面试官到底在考察什么很多候选人以为数据结构面试题不过是“背答案”只要把某本书上的题刷两遍就能过关。我自己面过几百人之后可以明确告诉你这个认知偏差是最大的坑。面试官问这类题目表面是在验证“这道题你会不会解”实际是从三个维度观察候选人。第一个维度是建模能力。给你一个场景描述比如“设计一个带过期时间的键值存储”“请实现一个支持随时返回当前最小值的栈”你能不能快速识别出这背后对应的数据结构模型。这个环节最直观的体现就是你是在那儿硬想解法还是能脱口而出“这题本质上是XX结构配合XX操作可以优化”。第二个维度是编码基本功。同样的题目候选人在白板上写出的代码差异非常大。边界条件有没有处理、循环退出条件判断是否正确、递归终止条件是否清晰这些细节决定了代码能不能一次跑通。我见过很多候选人思路完全正确但代码里出现索引越界、空指针访问这种失分太可惜。第三个维度是复杂度意识。写完了代码面试官一定会追问“时间复杂度是多少”“空间复杂度能不能再优化”。这一步考察的是候选人对算法开销的敏感度。能不能准确分析出最好情况、最坏情况和平均情况以及能不能在空间和时间之间做合理的权衡才是真正区分熟练度和死记硬背的分水岭。1.2 数据结构的整体脉络先理清在刷具体题目之前我建议把常用的数据结构先按一条线串起来。不要今天看链表明天看哈希表脑子里是散的。下面这个表格是我给内部同学做分享时常用的梳理方式按面试出现频率从高到低排列。数据结构核心特性典型应用场景面试频率数组连续内存、O(1)随机访问、扩容代价高双指针技巧、前缀和、矩阵遍历极高链表非连续存储、插入删除O(1)、查找O(n)反转链表、环形检测、LRU缓存极高栈与队列后进先出、先进先出括号匹配、单调栈、层序遍历高哈希表平均O(1)查询、需要解决冲突计数统计、缓存设计、去重极高树与二叉树层级结构、递归天然契合遍历、搜索、平衡树、堆高堆支持快速取最值、上浮下沉调整TopK问题、定时器、优先队列中高图节点关系建模、遍历复杂最短路径、拓扑排序、连通分量中你注意看这个表格数组和链表之所以频率极高是因为它们是最基础的存储载体其他高级结构底层几乎都是它们拼出来的。栈和队列虽然简单但喜欢和其他结构结合出题比如“用两个栈实现队列”这种设计题。1.3 复杂度分析要在写代码前就想清楚我的习惯是拿到一个题先别急着写代码在草稿纸上或心里把可能的方案过一遍预估出时间复杂度和空间复杂度再决定采用哪种写法。面试时最怕的不是说出一个次优解而是写完代码之后问复杂度发现连自己写的代码复杂度都说不清楚。这里分享一个快速估算法则单层循环一般就是O(n)双层循环是O(n^2)递归的复杂度要看递归深度和每层递归内部的操作。二叉树递归遍历的复杂度通常是O(n)因为每个节点恰好访问一次。如果是二分形式的递归如归并排序T(n)2T(n/2)O(n)解出来是O(n log n)。要把这些常见模式记熟现场推导反而容易出错。另外空间复杂度经常被忽略。很多候选人写出的代码能用但是额外开辟了一个同等规模的数组空间复杂度O(n)其实有时候通过指针或原地交换完全可以做到O(1)。面试官追问“能不能优化内存”时你的回答空间就在这里拉开。2. 高频线性表题目拆解2.1 数组类双指针是出场率最高的套路数组类题目里有一个被问了无数次但我始终觉得值得讲的题合并两个有序数组。给定两个按非递减顺序排列的数组要求把第二个数组合并到第一个数组中第一个数组的长度足够容纳两个数组的所有元素。这个问题最直观的思路是从前往后合并但这样每插入一个元素都要把后续元素往后移动时间复杂度会变成O(n^2)。更优的做法是从尾部开始遍历三个指针分别指向第一个数组的有效末尾、第二个数组的末尾、以及合并后数组的末尾从大到小填充。def merge(nums1, m, nums2, n): p1, p2 m - 1, n - 1 tail m n - 1 while p2 0: if p1 0 and nums1[p1] nums2[p2]: nums1[tail] nums1[p1] p1 - 1 else: nums1[tail] nums2[p2] p2 - 1 tail - 1这段代码的核心在于从尾部开始可以避免覆盖掉尚未处理的元素。面试官通常会顺着这个题问你“如果要求合并后不修改原数组空间复杂度怎么算”答案就是额外开一个数组O(mn)思路一样但方向相反。这类题目不复杂但能考察你对数组存储方式和双指针技巧的理解深度。另一个经典是“移动零”。给一个数组把其中的零全部移动到末尾同时保持非零元素的相对顺序。最优解法是快慢指针慢指针指向下一个非零元素应该放的位置快指针负责找非零元素找到就交换。这个题看起来简单但很多候选人会把写法复杂化或者忘记了交换后要把慢指针及时后移。如果现场让我给一个加分回答我会主动补充一句“这个思路本质上是稳定排序的雏形只记录零和非零两类元素的相对顺序。”2.2 链表类反转链表的三指针法必须形成肌肉记忆链表题在所有数据结构面试题里地位特殊因为它专门考察指针操作的基本功。反转链表是我认为是链表题的母题一旦掌握了它的递归和迭代两种写法后面很多题目都能复用。迭代写法是用三个指针prev、cur、next每次把cur.next指向prev然后三个指针整体向右移动。看起来简单但真正写的时候很多人会忘记保存临时节点导致链表断裂。我建议你在纸上先画一遍链表标出每一步之后每个节点的指向再写代码。def reverse_list(head): prev, cur None, head while cur: nxt cur.next cur.next prev prev cur cur nxt return prev递归写法更精简但不容易想通假设head之后的链表已经反转好了此时需要让原链表的下一个节点指向head本身然后head指向None。def reverse_list_recursive(head): if not head or not head.next: return head new_head reverse_list_recursive(head.next) head.next.next head head.next None return new_head面试时我一般推荐先写迭代版本因为它不容易出错复杂度也好解释。如果面试官追问“递归怎么写”再写递归不迟。反过来如果一上来就写递归性能上其实没有优势还容易暴露你对递归深度溢出的担忧考虑不周。2.3 环形链表检测快慢指针的临界条件最容易翻车“给一个链表判断是否存在环”也是老熟人。解法是快慢指针快指针每次走两步慢指针每次走一步如果存在环快慢指针必然会在某个节点相遇。这背后的物理意义是如果两个人绕圈跑速度不同迟早会相遇。我在面试现场见过最多的错误是只写循环不写退出条件。正确写法是循环里先判断slow和fast是否为空以及fast.next是否为空否则访问空指针的下一个节点直接抛异常。def has_cycle(head): slow fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True return False“为什么快指针每次走两步而不是三步”这是常见的追问。原因是走三步时快指针可能直接跳过了慢指针所在节点跨步太大会导致无法判断是否跨越了环的某个关键位置而且在处理环长度和步数关系的数学证明上会更复杂。两步是最简单且不会跳过相遇节点的选择。如果候选人能回答到这一层面试官对这道题的满意度基本就及格了。2.4 用两个栈实现队列考察数据结构组合设计“请你用两个栈实现一个队列完成push、pop、top、empty功能”几乎是每个候选人都会遇到的题。核心思路是入队时直接压入stack1出队时检查stack2是否为空如果为空则把stack1里的所有元素依次弹出并压入stack2再从stack2弹出队头元素。这个设计的精妙之处在于每个元素最多被移动两次入队一次出队前转移一次。因此均摊时间复杂度是O(1)虽然某一次出队可能触发大面积转移但整体均摊下来依然常数级。很多候选人能画出思路但代码实现时忘记判断stack2非空时不能直接转移导致顺序错乱这是最常见的错误。class MyQueue { private: stackint inStack; stackint outStack; public: void push(int x) { inStack.push(x); } int pop() { if (outStack.empty()) { while (!inStack.empty()) { outStack.push(inStack.top()); inStack.pop(); } } int res outStack.top(); outStack.pop(); return res; } };面试官经常接着问“那用两个队列实现一个栈怎么做”。这个要稍微区分一下入栈时直接把元素放入有元素的队列出栈时把队列中除了队尾元素外的所有元素转移到另一个队列然后弹出队尾元素。每次出栈操作复杂度是O(n)没有均摊优化空间。这两个题放一起对比记忆效率很高。3. 树与堆面试中最容易拉开差距的部分3.1 二叉树遍历递归版本和迭代版本都要熟练二叉树遍历几乎是所有树相关题目的基础。前序、中序、后序的递归写法没什么难度闭着眼睛都能写。但面试中经常要求你用一个显式栈写出迭代版本主要考察你是否真正理解了遍历过程和系统调用栈的关系。以中序遍历为例递归版本的逻辑就是“先左、再根、后右”。迭代版本需要模拟这个递归过程一路向下访问左子树把经过的节点全部压入栈左子树为空时弹出栈顶访问然后转入右子树继续。写成代码就是两个循环嵌套def inorder_traversal(root): result [] stack [] cur root while cur or stack: while cur: stack.append(cur) cur cur.left cur stack.pop() result.append(cur.val) cur cur.right return result我建议前序和中序的迭代写法重点练后序遍历因为需要额外标记节点访问状态可以直接用“前序反转”的思路简化对树进行根、右、左的遍历最后反转结果就是后序。这是工艺上常见的取巧方法面试时能讲清原理就没问题。3.2 二叉搜索树第K小节点用中序遍历的天然顺序解题二叉搜索树BST的特点是左子树所有节点小于根节点右子树所有节点大于根节点。因此对它进行中序遍历得到的就是有序序列。题目“找出BST中第K小的节点”的最简单解法就是中序遍历计数。这个题的加分点在于能否说明白递归版本的空间复杂度。如果使用递归中序遍历系统栈深等于树高最坏情况是高度为n的斜树栈空间O(n)。如果要求O(1)空间可以采用Morris遍历利用节点的空指针线索化临时修改树结构实现O(n)时间、O(1)空间的中序遍历。这个知识点属于进阶内容面试时如果主动提出往往是很大的亮点但前提是你真的理解它如何修改了空指针而不是背了个名词。核心实现思路 1. 初始化cur指向root 2. 如果cur.left为空访问curcur cur.right 3. 如果cur.left不为空找到cur左子树的最右节点mostRight 4. 如果mostRight.right为空令其指向cur然后cur cur.left 5. 如果mostRight.right已指向cur说明左子树已遍历完重置mostRight.right为空访问curcur cur.right3.3 堆的模拟实现上浮和下沉是算法的灵魂堆是一种特殊的完全二叉树满足父节点值小于等于小顶堆或大于等于大顶堆子节点值。面试中经典的题目是“实现一个小顶堆的入堆和出堆操作”这是堆排序以及TopK问题的底层基础。堆用数组表示时根节点放在索引0任意节点i的左右孩子索引分别是2i1和2i2父节点索引是(i-1)/2。入堆操作是把新元素放在数组末尾然后向上调整不断和父节点比较如果当前节点更小就交换直到满足堆序。出堆操作是取出堆顶最小值把数组末尾元素移到堆顶然后向下调整和两个孩子中较小的那个比较如果当前节点更大就交换。class MinHeap { private int[] data; private int size; public void push(int val) { data[size] val; int index size; size; while (index 0) { int parent (index - 1) / 2; if (data[parent] data[index]) { swap(data, parent, index); index parent; } else { break; } } } public int pop() { int res data[0]; data[0] data[size - 1]; size--; int index 0; while (2 * index 1 size) { int left 2 * index 1; int right left 1; int smaller left; if (right size data[right] data[left]) { smaller right; } if (data[index] data[smaller]) { swap(data, index, smaller); index smaller; } else { break; } } return res; } }这段代码我当年自己写的时候也犯过糊涂最大的问题是向下调整时没有判断右孩子是否存在。堆是完全二叉树左孩子可能存在而右孩子不存在如果直接用右孩子索引访问数组就会越界。加入right size这个判断之后才算是真正完整的实现。面试中如果能把上下调整两个函数的交换逻辑讲清楚堆相关的题基本都能顺畅衔接。4. 哈希与图从原理到高频场景题4.1 哈希冲突的几种处理方式都要能聊明白哈希表用O(1)的平均时间完成查找但它的前提是哈希函数设计合理冲突尽可能少。当冲突发生时面试官最常问的就是“如何处理冲突”。最常用的方法是链地址法每个桶存一个链表冲突的元素依次挂到链表里。Java标准库中HashMap在Java 8之后做了优化当链表长度超过8时转成红黑树把最坏情况下的查找复杂度从O(n)降到O(log n)。这个点值得记住它是典型的“用空间换时间、用复杂结构优化极端情况”的工程案例。另一种方法是开放地址法当某个位置被占用时按一定的探测序列寻找下一个空闲位置。常见的探测方式有线性探测、二次探测和双重散列。线性探测的问题是容易产生聚集现象也就是连续占用的槽位越来越多进而导致后续冲突概率增加。双重散列可以明显缓解这个问题但需要设计两个不同的哈希函数工程复杂度更高。面试回答的时候建议把两种方法做一个对比说明各自适合的场景。链地址法更适合元素总数不确定、哈希表可能扩容的情况开放地址法更适合数据规模确定、内存敏感的场景比如操作系统内核里的某些哈希表就常用开放地址法避免链表节点开销。4.2 LRU缓存哈希表加双向链表的经典组合LRULeast Recently Used最近最少使用的题目在面试中一直很稳定因为它综合考察了哈希表随机访问能力和链表有序性是一个组合设计题。题目要求实现一个支持get和put操作的缓存容量有限当缓存满时淘汰最久未使用的数据。这里的关键点有两个get操作要学会“提到最前”的语义put操作要处理好容量满时的淘汰逻辑。为什么不直接用数组存访问时间戳因为寻找最久未使用的元素需要扫描全部缓存时间O(n)不可接受。所以经典方案是哈希表存key到链表的节点引用双向链表按访问时间顺序维护所有key。class LRUCache { private int capacity; private MapInteger, Node map; private Node head; private Node tail; public int get(int key) { if (!map.containsKey(key)) return -1; Node node map.get(key); moveToHead(node); return node.value; } public void put(int key, int value) { if (map.containsKey(key)) { Node node map.get(key); node.value value; moveToHead(node); } else { if (map.size() capacity) { Node removed removeTail(); map.remove(removed.key); } Node node new Node(key, value); addToHead(node); map.put(key, node); } } }我面试的时候会让候选人把双向链表画出来解释为什么是双向而不是单向。因为删除链表尾部节点时如果只有单向链表需要遍历找到倒数第二个节点复杂度退化为O(n)。加了前驱指针之后尾部删除就变成O(1)了。很多候选人能实现哈希表和链表的逻辑但会在维护链表节点时忘记更新前驱指针的next或者后继指针的prev这类细节如果不画图写起来非常容易出错。4.3 图的最短路径Dijkstra算法的关键在贪心选择图相关的面试题相对较少直接让写完整算法但最短路径是一个非常经典的提问切入点。Dijkstra算法用于解决单源非负权最短路径核心思想是每次从未确定的节点中选一个距离源点最近的节点用它去松弛相邻节点。这个过程天然适合用优先队列堆来维护当前距离最小的候选节点。def dijkstra(graph, start): import heapq distances {node: float(inf) for node in graph} distances[start] 0 pq [(0, start)] while pq: d, node heapq.heappop(pq) if d distances[node]: continue for neighbor, weight in graph[node].items(): nd d weight if nd distances[neighbor]: distances[neighbor] nd heapq.heappush(pq, (nd, neighbor)) return distances面试官往往不会要求你逐行实现但希望你讲清楚为什么每次选择当前最小距离节点是安全的、为什么这个贪心策略在存在负权边时会失效。负权边可能让一个已经确定最短路径的节点后续通过负边得到更短路径破坏贪心前提所以Dijkstra不适用于带负权边的图。如果图中存在负权边需要用Bellman-Ford算法它通过多轮松弛来确保正确性。能把三者的适用场景区分清楚这类题目的回答水准就上来了。5. 代码实现中的常见纰漏与排查实录5.1 边界条件最容易翻车的三处在整理面试题的过程中我发现候选人的代码问题高度集中在三个边界条件上。第一个是空输入。链表类的题目head可能为null数组类的题目输入数组可能为空。我建议你养成习惯在函数入口处直接判断空或长度为零的情况提前返回避免后续访问报错。在面试中主动写下空值判断往往会被视为考虑全面的信号。第二个是循环终止条件。链表遍历时while循环里到底写cur还是cur.next数组双指针时while循环是left right还是left right这些差一个符号都可能导致死循环或漏处理最后一个元素。我的统一习惯是涉及数组常用left right左闭右闭区间涉及链表则用cur ! None为主只有在需要访问cur.next时才额外判断。第三个是索引越界。数组题里最常见的错误就是访问index1或index-1时没有判断边界。比如快慢指针题里虽然已经判断fast不为空但还是会去访问fast.next.next如果链表长度刚好是偶数这就可能空指针。每次写数组或链表索引的下一跳都问自己一句“这里会不会访问到不存在的位置。”5.2 递归改迭代栈模拟的两种姿势面试中经常遇到“你写的是递归能不能改成非递归”的追问。表面上看是考查代码能力实际上是在考察你对递归调用过程的理解。我在实际面评里见过一个不错的分类方法递归改写迭代大体就两种思路。第一种是显式栈模拟系统栈适用于深度优先遍历类问题。每次都把当前状态压入栈循环中弹出状态进行处理需要时把新状态再压入栈。二叉树迭代遍历就是最典型的例子。第二种是动态规划类递归的自底向上改写把递归改成数组递推空间通常可以优化。比如斐波那契数列的递归改循环只保留两个前驱变量。我自己的经验是写递归代码时先清晰描述递归函数的语义比如“这个函数返回以root为根的树的最大深度”然后确定递归出口最后把子问题的结果组合成原问题的解。按这个顺序来不容易写到一半思路断掉。改成迭代时再回归到递归展开的实际执行顺序去设计栈的压入顺序不要凭空硬记模板。5.3 面试写代码的速查清单最后把自己整理的速查清单放这里每次模拟面试或者真实面试前都可以快速过一遍。题目读两遍先讲思路再动手。最好给面试官一个“这道题我打算用XX结构时间复杂度预估计是XX”的预告。空值处理链表头节点是否为空、数组长度是否为零、二叉树的根是否为空。循环边界while里的条件是否覆盖最后一个元素是否会死循环。指针移动链表中prev、cur、next三个指针是否在每次循环都正确更新。递归出口递归函数是否有明确的终止条件递归深度最坏是多少。索引访问数组访问前确认索引范围特别是index1、index-1、2*index2这些位置。复杂度分析写完代码立刻总结时间和空间复杂度并主动说明能否优化。测试用例用常规输入、空输入、单元素输入、极端值输入各跑一遍口头走查一遍代码。按照这个清单能在很大程度上避免“思路对了但代码翻车”的遗憾。6. 一些不算技巧的体会做了这几年面试官又把这些题目重新整理了一遍我个人最深的感受是数据结构面试题看似是背题其实最终拼的是对每一类结构本质特征的理解。数组靠随机访问取胜链表的优势是插入删除灵活栈和队列定义了一类受限但清晰的操作模型树和堆通过层级关系让搜索和极值查找变得高效哈希表用空间换时间。当你遇到一个题目能自动联想到这些特征答案往往就呼之欲出了。整理答案的过程我建议不要依赖现成的背诵版本而是自己完整地推导一遍最优解的思考路径。从暴力解法开始分析瓶颈在哪一步再优化掉这个瓶颈比直接记住“这题用栈”要有用得多。因为面试官看重的从来不只是结果而是你展示出来的思维链条。还有一个实用的小建议给自己准备一个错题本不用分类只记录每次写错的边界条件、卡住过的指针操作、忘记考虑的复杂度细节。间隔一周之后重新做一遍错题对标红的地方做二次标记重点复习。这样坚持几周数据结构面试题的基本功会明显扎实起来。 
长河君 · 2026/10/20 16:11:24 · 阅读 1.2k 数据结构面试题及答案整理：高频考点与解题思路精讲
数据结构面试题以及答案整理这个话题我最近花了大概两周时间重新梳理了一遍。之前在中型技术团队做过几年后端开发也协助部门做过不少轮校招和社招的技术面试坦白说数据结构的题目是最能快速暴露候选人基本功的环节。同一个题有的人十分钟写完还主动讲了优化方案有的人半小时才勉强跑通。今天把常见的高频题、完整的答题思路、以及我实际做面试官时观察到的高频失分点一次性整理出来给正在准备的朋友做个参考。1. 为什么数据结构面试题值得逐题吃透1.1 面试官到底在考察什么很多候选人以为数据结构面试题不过是“背答案”只要把某本书上的题刷两遍就能过关。我自己面过几百人之后可以明确告诉你这个认知偏差是最大的坑。面试官问这类题目表面是在验证“这道题你会不会解”实际是从三个维度观察候选人。第一个维度是建模能力。给你一个场景描述比如“设计一个带过期时间的键值存储”“请实现一个支持随时返回当前最小值的栈”你能不能快速识别出这背后对应的数据结构模型。这个环节最直观的体现就是你是在那儿硬想解法还是能脱口而出“这题本质上是XX结构配合XX操作可以优化”。第二个维度是编码基本功。同样的题目候选人在白板上写出的代码差异非常大。边界条件有没有处理、循环退出条件判断是否正确、递归终止条件是否清晰这些细节决定了代码能不能一次跑通。我见过很多候选人思路完全正确但代码里出现索引越界、空指针访问这种失分太可惜。第三个维度是复杂度意识。写完了代码面试官一定会追问“时间复杂度是多少”“空间复杂度能不能再优化”。这一步考察的是候选人对算法开销的敏感度。能不能准确分析出最好情况、最坏情况和平均情况以及能不能在空间和时间之间做合理的权衡才是真正区分熟练度和死记硬背的分水岭。1.2 数据结构的整体脉络先理清在刷具体题目之前我建议把常用的数据结构先按一条线串起来。不要今天看链表明天看哈希表脑子里是散的。下面这个表格是我给内部同学做分享时常用的梳理方式按面试出现频率从高到低排列。数据结构核心特性典型应用场景面试频率数组连续内存、O(1)随机访问、扩容代价高双指针技巧、前缀和、矩阵遍历极高链表非连续存储、插入删除O(1)、查找O(n)反转链表、环形检测、LRU缓存极高栈与队列后进先出、先进先出括号匹配、单调栈、层序遍历高哈希表平均O(1)查询、需要解决冲突计数统计、缓存设计、去重极高树与二叉树层级结构、递归天然契合遍历、搜索、平衡树、堆高堆支持快速取最值、上浮下沉调整TopK问题、定时器、优先队列中高图节点关系建模、遍历复杂最短路径、拓扑排序、连通分量中你注意看这个表格数组和链表之所以频率极高是因为它们是最基础的存储载体其他高级结构底层几乎都是它们拼出来的。栈和队列虽然简单但喜欢和其他结构结合出题比如“用两个栈实现队列”这种设计题。1.3 复杂度分析要在写代码前就想清楚我的习惯是拿到一个题先别急着写代码在草稿纸上或心里把可能的方案过一遍预估出时间复杂度和空间复杂度再决定采用哪种写法。面试时最怕的不是说出一个次优解而是写完代码之后问复杂度发现连自己写的代码复杂度都说不清楚。这里分享一个快速估算法则单层循环一般就是O(n)双层循环是O(n^2)递归的复杂度要看递归深度和每层递归内部的操作。二叉树递归遍历的复杂度通常是O(n)因为每个节点恰好访问一次。如果是二分形式的递归如归并排序T(n)2T(n/2)O(n)解出来是O(n log n)。要把这些常见模式记熟现场推导反而容易出错。另外空间复杂度经常被忽略。很多候选人写出的代码能用但是额外开辟了一个同等规模的数组空间复杂度O(n)其实有时候通过指针或原地交换完全可以做到O(1)。面试官追问“能不能优化内存”时你的回答空间就在这里拉开。2. 高频线性表题目拆解2.1 数组类双指针是出场率最高的套路数组类题目里有一个被问了无数次但我始终觉得值得讲的题合并两个有序数组。给定两个按非递减顺序排列的数组要求把第二个数组合并到第一个数组中第一个数组的长度足够容纳两个数组的所有元素。这个问题最直观的思路是从前往后合并但这样每插入一个元素都要把后续元素往后移动时间复杂度会变成O(n^2)。更优的做法是从尾部开始遍历三个指针分别指向第一个数组的有效末尾、第二个数组的末尾、以及合并后数组的末尾从大到小填充。def merge(nums1, m, nums2, n): p1, p2 m - 1, n - 1 tail m n - 1 while p2 0: if p1 0 and nums1[p1] nums2[p2]: nums1[tail] nums1[p1] p1 - 1 else: nums1[tail] nums2[p2] p2 - 1 tail - 1这段代码的核心在于从尾部开始可以避免覆盖掉尚未处理的元素。面试官通常会顺着这个题问你“如果要求合并后不修改原数组空间复杂度怎么算”答案就是额外开一个数组O(mn)思路一样但方向相反。这类题目不复杂但能考察你对数组存储方式和双指针技巧的理解深度。另一个经典是“移动零”。给一个数组把其中的零全部移动到末尾同时保持非零元素的相对顺序。最优解法是快慢指针慢指针指向下一个非零元素应该放的位置快指针负责找非零元素找到就交换。这个题看起来简单但很多候选人会把写法复杂化或者忘记了交换后要把慢指针及时后移。如果现场让我给一个加分回答我会主动补充一句“这个思路本质上是稳定排序的雏形只记录零和非零两类元素的相对顺序。”2.2 链表类反转链表的三指针法必须形成肌肉记忆链表题在所有数据结构面试题里地位特殊因为它专门考察指针操作的基本功。反转链表是我认为是链表题的母题一旦掌握了它的递归和迭代两种写法后面很多题目都能复用。迭代写法是用三个指针prev、cur、next每次把cur.next指向prev然后三个指针整体向右移动。看起来简单但真正写的时候很多人会忘记保存临时节点导致链表断裂。我建议你在纸上先画一遍链表标出每一步之后每个节点的指向再写代码。def reverse_list(head): prev, cur None, head while cur: nxt cur.next cur.next prev prev cur cur nxt return prev递归写法更精简但不容易想通假设head之后的链表已经反转好了此时需要让原链表的下一个节点指向head本身然后head指向None。def reverse_list_recursive(head): if not head or not head.next: return head new_head reverse_list_recursive(head.next) head.next.next head head.next None return new_head面试时我一般推荐先写迭代版本因为它不容易出错复杂度也好解释。如果面试官追问“递归怎么写”再写递归不迟。反过来如果一上来就写递归性能上其实没有优势还容易暴露你对递归深度溢出的担忧考虑不周。2.3 环形链表检测快慢指针的临界条件最容易翻车“给一个链表判断是否存在环”也是老熟人。解法是快慢指针快指针每次走两步慢指针每次走一步如果存在环快慢指针必然会在某个节点相遇。这背后的物理意义是如果两个人绕圈跑速度不同迟早会相遇。我在面试现场见过最多的错误是只写循环不写退出条件。正确写法是循环里先判断slow和fast是否为空以及fast.next是否为空否则访问空指针的下一个节点直接抛异常。def has_cycle(head): slow fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True return False“为什么快指针每次走两步而不是三步”这是常见的追问。原因是走三步时快指针可能直接跳过了慢指针所在节点跨步太大会导致无法判断是否跨越了环的某个关键位置而且在处理环长度和步数关系的数学证明上会更复杂。两步是最简单且不会跳过相遇节点的选择。如果候选人能回答到这一层面试官对这道题的满意度基本就及格了。2.4 用两个栈实现队列考察数据结构组合设计“请你用两个栈实现一个队列完成push、pop、top、empty功能”几乎是每个候选人都会遇到的题。核心思路是入队时直接压入stack1出队时检查stack2是否为空如果为空则把stack1里的所有元素依次弹出并压入stack2再从stack2弹出队头元素。这个设计的精妙之处在于每个元素最多被移动两次入队一次出队前转移一次。因此均摊时间复杂度是O(1)虽然某一次出队可能触发大面积转移但整体均摊下来依然常数级。很多候选人能画出思路但代码实现时忘记判断stack2非空时不能直接转移导致顺序错乱这是最常见的错误。class MyQueue { private: stackint inStack; stackint outStack; public: void push(int x) { inStack.push(x); } int pop() { if (outStack.empty()) { while (!inStack.empty()) { outStack.push(inStack.top()); inStack.pop(); } } int res outStack.top(); outStack.pop(); return res; } };面试官经常接着问“那用两个队列实现一个栈怎么做”。这个要稍微区分一下入栈时直接把元素放入有元素的队列出栈时把队列中除了队尾元素外的所有元素转移到另一个队列然后弹出队尾元素。每次出栈操作复杂度是O(n)没有均摊优化空间。这两个题放一起对比记忆效率很高。3. 树与堆面试中最容易拉开差距的部分3.1 二叉树遍历递归版本和迭代版本都要熟练二叉树遍历几乎是所有树相关题目的基础。前序、中序、后序的递归写法没什么难度闭着眼睛都能写。但面试中经常要求你用一个显式栈写出迭代版本主要考察你是否真正理解了遍历过程和系统调用栈的关系。以中序遍历为例递归版本的逻辑就是“先左、再根、后右”。迭代版本需要模拟这个递归过程一路向下访问左子树把经过的节点全部压入栈左子树为空时弹出栈顶访问然后转入右子树继续。写成代码就是两个循环嵌套def inorder_traversal(root): result [] stack [] cur root while cur or stack: while cur: stack.append(cur) cur cur.left cur stack.pop() result.append(cur.val) cur cur.right return result我建议前序和中序的迭代写法重点练后序遍历因为需要额外标记节点访问状态可以直接用“前序反转”的思路简化对树进行根、右、左的遍历最后反转结果就是后序。这是工艺上常见的取巧方法面试时能讲清原理就没问题。3.2 二叉搜索树第K小节点用中序遍历的天然顺序解题二叉搜索树BST的特点是左子树所有节点小于根节点右子树所有节点大于根节点。因此对它进行中序遍历得到的就是有序序列。题目“找出BST中第K小的节点”的最简单解法就是中序遍历计数。这个题的加分点在于能否说明白递归版本的空间复杂度。如果使用递归中序遍历系统栈深等于树高最坏情况是高度为n的斜树栈空间O(n)。如果要求O(1)空间可以采用Morris遍历利用节点的空指针线索化临时修改树结构实现O(n)时间、O(1)空间的中序遍历。这个知识点属于进阶内容面试时如果主动提出往往是很大的亮点但前提是你真的理解它如何修改了空指针而不是背了个名词。核心实现思路 1. 初始化cur指向root 2. 如果cur.left为空访问curcur cur.right 3. 如果cur.left不为空找到cur左子树的最右节点mostRight 4. 如果mostRight.right为空令其指向cur然后cur cur.left 5. 如果mostRight.right已指向cur说明左子树已遍历完重置mostRight.right为空访问curcur cur.right3.3 堆的模拟实现上浮和下沉是算法的灵魂堆是一种特殊的完全二叉树满足父节点值小于等于小顶堆或大于等于大顶堆子节点值。面试中经典的题目是“实现一个小顶堆的入堆和出堆操作”这是堆排序以及TopK问题的底层基础。堆用数组表示时根节点放在索引0任意节点i的左右孩子索引分别是2i1和2i2父节点索引是(i-1)/2。入堆操作是把新元素放在数组末尾然后向上调整不断和父节点比较如果当前节点更小就交换直到满足堆序。出堆操作是取出堆顶最小值把数组末尾元素移到堆顶然后向下调整和两个孩子中较小的那个比较如果当前节点更大就交换。class MinHeap { private int[] data; private int size; public void push(int val) { data[size] val; int index size; size; while (index 0) { int parent (index - 1) / 2; if (data[parent] data[index]) { swap(data, parent, index); index parent; } else { break; } } } public int pop() { int res data[0]; data[0] data[size - 1]; size--; int index 0; while (2 * index 1 size) { int left 2 * index 1; int right left 1; int smaller left; if (right size data[right] data[left]) { smaller right; } if (data[index] data[smaller]) { swap(data, index, smaller); index smaller; } else { break; } } return res; } }这段代码我当年自己写的时候也犯过糊涂最大的问题是向下调整时没有判断右孩子是否存在。堆是完全二叉树左孩子可能存在而右孩子不存在如果直接用右孩子索引访问数组就会越界。加入right size这个判断之后才算是真正完整的实现。面试中如果能把上下调整两个函数的交换逻辑讲清楚堆相关的题基本都能顺畅衔接。4. 哈希与图从原理到高频场景题4.1 哈希冲突的几种处理方式都要能聊明白哈希表用O(1)的平均时间完成查找但它的前提是哈希函数设计合理冲突尽可能少。当冲突发生时面试官最常问的就是“如何处理冲突”。最常用的方法是链地址法每个桶存一个链表冲突的元素依次挂到链表里。Java标准库中HashMap在Java 8之后做了优化当链表长度超过8时转成红黑树把最坏情况下的查找复杂度从O(n)降到O(log n)。这个点值得记住它是典型的“用空间换时间、用复杂结构优化极端情况”的工程案例。另一种方法是开放地址法当某个位置被占用时按一定的探测序列寻找下一个空闲位置。常见的探测方式有线性探测、二次探测和双重散列。线性探测的问题是容易产生聚集现象也就是连续占用的槽位越来越多进而导致后续冲突概率增加。双重散列可以明显缓解这个问题但需要设计两个不同的哈希函数工程复杂度更高。面试回答的时候建议把两种方法做一个对比说明各自适合的场景。链地址法更适合元素总数不确定、哈希表可能扩容的情况开放地址法更适合数据规模确定、内存敏感的场景比如操作系统内核里的某些哈希表就常用开放地址法避免链表节点开销。4.2 LRU缓存哈希表加双向链表的经典组合LRULeast Recently Used最近最少使用的题目在面试中一直很稳定因为它综合考察了哈希表随机访问能力和链表有序性是一个组合设计题。题目要求实现一个支持get和put操作的缓存容量有限当缓存满时淘汰最久未使用的数据。这里的关键点有两个get操作要学会“提到最前”的语义put操作要处理好容量满时的淘汰逻辑。为什么不直接用数组存访问时间戳因为寻找最久未使用的元素需要扫描全部缓存时间O(n)不可接受。所以经典方案是哈希表存key到链表的节点引用双向链表按访问时间顺序维护所有key。class LRUCache { private int capacity; private MapInteger, Node map; private Node head; private Node tail; public int get(int key) { if (!map.containsKey(key)) return -1; Node node map.get(key); moveToHead(node); return node.value; } public void put(int key, int value) { if (map.containsKey(key)) { Node node map.get(key); node.value value; moveToHead(node); } else { if (map.size() capacity) { Node removed removeTail(); map.remove(removed.key); } Node node new Node(key, value); addToHead(node); map.put(key, node); } } }我面试的时候会让候选人把双向链表画出来解释为什么是双向而不是单向。因为删除链表尾部节点时如果只有单向链表需要遍历找到倒数第二个节点复杂度退化为O(n)。加了前驱指针之后尾部删除就变成O(1)了。很多候选人能实现哈希表和链表的逻辑但会在维护链表节点时忘记更新前驱指针的next或者后继指针的prev这类细节如果不画图写起来非常容易出错。4.3 图的最短路径Dijkstra算法的关键在贪心选择图相关的面试题相对较少直接让写完整算法但最短路径是一个非常经典的提问切入点。Dijkstra算法用于解决单源非负权最短路径核心思想是每次从未确定的节点中选一个距离源点最近的节点用它去松弛相邻节点。这个过程天然适合用优先队列堆来维护当前距离最小的候选节点。def dijkstra(graph, start): import heapq distances {node: float(inf) for node in graph} distances[start] 0 pq [(0, start)] while pq: d, node heapq.heappop(pq) if d distances[node]: continue for neighbor, weight in graph[node].items(): nd d weight if nd distances[neighbor]: distances[neighbor] nd heapq.heappush(pq, (nd, neighbor)) return distances面试官往往不会要求你逐行实现但希望你讲清楚为什么每次选择当前最小距离节点是安全的、为什么这个贪心策略在存在负权边时会失效。负权边可能让一个已经确定最短路径的节点后续通过负边得到更短路径破坏贪心前提所以Dijkstra不适用于带负权边的图。如果图中存在负权边需要用Bellman-Ford算法它通过多轮松弛来确保正确性。能把三者的适用场景区分清楚这类题目的回答水准就上来了。5. 代码实现中的常见纰漏与排查实录5.1 边界条件最容易翻车的三处在整理面试题的过程中我发现候选人的代码问题高度集中在三个边界条件上。第一个是空输入。链表类的题目head可能为null数组类的题目输入数组可能为空。我建议你养成习惯在函数入口处直接判断空或长度为零的情况提前返回避免后续访问报错。在面试中主动写下空值判断往往会被视为考虑全面的信号。第二个是循环终止条件。链表遍历时while循环里到底写cur还是cur.next数组双指针时while循环是left right还是left right这些差一个符号都可能导致死循环或漏处理最后一个元素。我的统一习惯是涉及数组常用left right左闭右闭区间涉及链表则用cur ! None为主只有在需要访问cur.next时才额外判断。第三个是索引越界。数组题里最常见的错误就是访问index1或index-1时没有判断边界。比如快慢指针题里虽然已经判断fast不为空但还是会去访问fast.next.next如果链表长度刚好是偶数这就可能空指针。每次写数组或链表索引的下一跳都问自己一句“这里会不会访问到不存在的位置。”5.2 递归改迭代栈模拟的两种姿势面试中经常遇到“你写的是递归能不能改成非递归”的追问。表面上看是考查代码能力实际上是在考察你对递归调用过程的理解。我在实际面评里见过一个不错的分类方法递归改写迭代大体就两种思路。第一种是显式栈模拟系统栈适用于深度优先遍历类问题。每次都把当前状态压入栈循环中弹出状态进行处理需要时把新状态再压入栈。二叉树迭代遍历就是最典型的例子。第二种是动态规划类递归的自底向上改写把递归改成数组递推空间通常可以优化。比如斐波那契数列的递归改循环只保留两个前驱变量。我自己的经验是写递归代码时先清晰描述递归函数的语义比如“这个函数返回以root为根的树的最大深度”然后确定递归出口最后把子问题的结果组合成原问题的解。按这个顺序来不容易写到一半思路断掉。改成迭代时再回归到递归展开的实际执行顺序去设计栈的压入顺序不要凭空硬记模板。5.3 面试写代码的速查清单最后把自己整理的速查清单放这里每次模拟面试或者真实面试前都可以快速过一遍。题目读两遍先讲思路再动手。最好给面试官一个“这道题我打算用XX结构时间复杂度预估计是XX”的预告。空值处理链表头节点是否为空、数组长度是否为零、二叉树的根是否为空。循环边界while里的条件是否覆盖最后一个元素是否会死循环。指针移动链表中prev、cur、next三个指针是否在每次循环都正确更新。递归出口递归函数是否有明确的终止条件递归深度最坏是多少。索引访问数组访问前确认索引范围特别是index1、index-1、2*index2这些位置。复杂度分析写完代码立刻总结时间和空间复杂度并主动说明能否优化。测试用例用常规输入、空输入、单元素输入、极端值输入各跑一遍口头走查一遍代码。按照这个清单能在很大程度上避免“思路对了但代码翻车”的遗憾。6. 一些不算技巧的体会做了这几年面试官又把这些题目重新整理了一遍我个人最深的感受是数据结构面试题看似是背题其实最终拼的是对每一类结构本质特征的理解。数组靠随机访问取胜链表的优势是插入删除灵活栈和队列定义了一类受限但清晰的操作模型树和堆通过层级关系让搜索和极值查找变得高效哈希表用空间换时间。当你遇到一个题目能自动联想到这些特征答案往往就呼之欲出了。整理答案的过程我建议不要依赖现成的背诵版本而是自己完整地推导一遍最优解的思考路径。从暴力解法开始分析瓶颈在哪一步再优化掉这个瓶颈比直接记住“这题用栈”要有用得多。因为面试官看重的从来不只是结果而是你展示出来的思维链条。还有一个实用的小建议给自己准备一个错题本不用分类只记录每次写错的边界条件、卡住过的指针操作、忘记考虑的复杂度细节。间隔一周之后重新做一遍错题对标红的地方做二次标记重点复习。这样坚持几周数据结构面试题的基本功会明显扎实起来。