C++面试高频数据结构与算法考点：链表、二叉树与排序题精讲

说句实话，数据结构与算法这块，几乎是C++面试里最没法临时抱佛脚的部分。前三篇聊了语法、面向对象和内存，到了这一篇，考察方式完全不一样：不是问你“知不知道”，而是让你当场写、当场讲、当场证明。我见过不少候选人，八股背得滚瓜烂熟，一上手写链表就露馅，指针指到怀疑人生。这篇就来拆解面试中出现频率最高的几类数据结构与算法题，重点不是贴题解，而是把每类题目背后的考察意图、边界条件、C++实现细节和临场表达讲清楚。

1. 链表题：别只背代码，要理解指针操作的边界

链表题基本是面试手撕代码的第一关，不是因为难，而是因为它同时考两件事：对指针操作的熟练度，以及对边界条件的敏感度。C++里链表节点通常长这样：

struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} };

就这么几行，但能玩出无数花样。面试官想看的，不是你默写过多少遍题解，而是当next指针该断没断、该接没接的时候，你脑子里有没有那张“指针连接”的画面。

1.1 反转链表：迭代里的指针顺序是关键

反转链表绝对是登场率最高的题目，没有之一。迭代写法本身不长，但几乎每个人第一次写都会在某个地方卡住：

ListNode* reverseList(ListNode* head) { ListNode* prev = nullptr; ListNode* cur = head; while (cur) { ListNode* next = cur->next; // 先保存下一个节点 cur->next = prev; // 当前节点指向前一个节点 prev = cur; // 前一个节点移动到当前 cur = next; // 当前节点移动到下一个 } return prev; }

核心就一句：改cur->next之前，必须先存next。很多人脑子一热，上来就写cur->next = prev，结果next丢了，整个链表后面全断掉。这个动作的实质是：把每个节点的next方向调转，需要三根指针同时移动，prev是已经反转好的链头，cur是当前待处理节点，next是还没来得及处理的剩余链头。

面试中还有一个高频追问：用递归写一遍。递归版的核心是信任“子问题已经解决”：

ListNode* reverseList(ListNode* head) { if (!head || !head->next) return head; ListNode* newHead = reverseList(head->next); head->next->next = head; head->next = nullptr; return newHead; }

这题递归的难点在于：反转后head成了尾节点，必须要让head->next = nullptr，否则链表就带环了。面试官追问递归时，大概率不是考察你背没背过，而是想看你有没有理解递归的“归”这一步在做什么。

1.2 哨兵节点到底帮我们解决了什么

“可能修改头节点”的链表题，第一反应就是加dummy节点。经典场景是删除倒数第N个节点、合并两个有序链表、删除有序链表中的重复元素。

以删除倒数第N个节点为例，如果不用dummy，就得特判“删除的是不是头节点”：

ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy = new ListNode(0); dummy->next = head; ListNode* first = dummy; ListNode* second = dummy; for (int i = 0; i <= n; ++i) first = first->next; while (first) { first = first->next; second = second->next; } second->next = second->next->next; return dummy->next; }

这里的dummy节点，价值不是“多了一个节点”，而是让头节点跟其他普通节点的处理逻辑完全统一。最后return dummy->next而不是return head，因为原来的head可能已经被删掉了。这个细节我面试时被问过，答不上来会显得对链表操作缺乏整体把握。

1.3 链表题里的两个C++专属考点

链表题除了算法本身，经常夹带C++语言细节。最常见的两个：

第一个是形参修改。如果要在函数里修改head指针本身（比如把链表头换掉），需要用ListNode*&或者ListNode**传入。只修改节点内部next指针的话，传ListNode就够了。这个区分很多人搞不懂，其实是C++基本功。反转链表返回新头，所以函数返回ListNode没有问题；但如果写一个void reverseList(ListNode* head)，里面把head重新赋值，那是对函数内的局部变量赋值，外界的head不会变。

第二个是内存归属。删除节点后到底要不要delete？这取决于链表内存是new出来的还是栈上/池子里管理的。面试时最好主动确认：“这个链表的节点需要我负责释放吗？”如果不问直接delete，可能double-free；不问也不delete，则可能内存泄漏。这个决策本身，就在考察工程意识。

2. 排序类题目：复杂度要能讲出道理来

排序算法在面试里很少单独要求完整默写，但经常以两种形式出现：一是作为其他算法的基础操作，比如归并排序的合并函数被拿去统计逆序对；二是追问排序算法的复杂度、稳定性和适用场景。很多人能背出“快排O(nlogn)”但解释不了为什么，面试官只要追问一句就露馅。

2.1 快排的partition两种写法要心里有数

快排核心是partition。最常见的两种写法是Lomuto分区和Hoare分区。如果面试官让你写快排，我建议先写简洁的Lomuto：

int partition(vector<int>& nums, int left, int right) { int pivot = nums[right]; int i = left; for (int j = left; j < right; ++j) { if (nums[j] < pivot) { swap(nums[i], nums[j]); ++i; } } swap(nums[i], nums[right]); return i; }

这段代码维护的循环不变量是：[left, i)区间内所有元素都小于pivot，[i, j)区间内所有元素都大于等于pivot。每次遇到小于pivot的元素，就把它换到前面。这种写法好理解、不易错，适合面试现场。

但面试官很可能追问：如果数组已经有序，这种写法会怎样？答案是对应了O(n²)的最坏情况。解法是随机选基准或三数取中。当你能主动说出“对于基本有序的输入，应该用随机化基准来避免退化”，面试官对你的评价会上一个档次。

2.2 归并排序：链表排序的钥匙

链表的归并排序几乎必考，因为基于数组的排序大多依赖随机访问，链表不行，而归并排序天然适合链式结构。核心就三步：找中点、递归排序两半、合并。

找中点用快慢指针，这个我在第一部分提过。合并两个有序链表的逻辑也简单。完整代码大概长这样：

ListNode* sortList(ListNode* head) { if (!head || !head->next) return head; // 快慢指针找中点 ListNode* slow = head; ListNode* fast = head->next; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } ListNode* mid = slow->next; slow->next = nullptr; // 断开链表 ListNode* left = sortList(head); ListNode* right = sortList(mid); return mergeTwoLists(left, right); }

这里有一个很容易出错的细节：快指针fast初始化是head->next而不是head，这样在处理偶数长度节点时，slow最后停在偏左的位置，保证断开的左右两部分长度差不超过1。如果fast从head开始，偶数时slow会偏右，递归划分则不均匀。这个坑我实际写的时候踩过，面试时看别人写也见过好多次。

2.3 排序算法速查与工程选型逻辑

我整理了一张经常在面试题里出现的排序对比表，建议自己动手推一遍复杂度是怎么来的，而不是干背：

稳定性这个点特别容易考。什么是稳定排序？值相同的关键字在排序后相对顺序不变。什么场景需要？比如先按时间排序再按优先级排序，后一个排序不能破坏前一个排序的结果。工程里std::sort为什么通常不稳定？因为标准要求的是平均O(nlogn)且可能采取快排优化（内省排序）；std::stable_sort则是归并思想实现，稳定但可能占用额外空间。这些细节写在简历上，面试官一追问就有内容可聊。

3. 二叉树题目：高频考点的解题模板与边界思维

二叉树题目在面试中的出现率高得惊人，但好消息是，大部分题都有套路。掌握几种范式之后，很多题都是模板的变体。真正区分水平的，是递归的返回语义设计、终止条件选择、以及最坏空间复杂度分析方式。

3.1 递归遍历与迭代遍历的对应关系

二叉树的递归遍历只要想清楚三件事就能写：当前节点做什么、左右子树递归调用返回什么、终止条件是什么。以最大深度为例：

int maxDepth(TreeNode* root) { if (!root) return 0; int leftDepth = maxDepth(root->left); int rightDepth = maxDepth(root->right); return max(leftDepth, rightDepth) + 1; }

这题最简单的写法只需要3行，但面试官常追问：递归改迭代怎么做？这个问题背后的意图是考察你对“函数调用栈”的理解。手动用栈模拟时，要自己管理节点状态。我推荐统一模板：标记法。

// 中序遍历的迭代写法，用栈模拟递归 vector<int> inorderTraversal(TreeNode* root) { vector<int> result; stack<TreeNode*> stk; TreeNode* cur = root; while (cur || !stk.empty()) { while (cur) { stk.push(cur); cur = cur->left; } cur = stk.top(); stk.pop(); result.push_back(cur->val); cur = cur->right; } return result; }

如果面试要求写层序遍历，则用queue就对了，每层循环前先记录当前队列大小，这个size就是本层节点数。层序遍历+BFS经常与“判断是否为对称二叉树”“按层输出”“二叉树的右视图”等题配套考察。

3.2 构造类与公共祖先类的思路

构造类题目经典的是“从前序与中序遍历序列构造二叉树”。核心逻辑是：前序第一个元素是根，在中序里找到根的位置，左边是左子树，右边是右子树，然后递归构建。

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { // 用哈希表记录中序位置，避免每次遍历查找 unordered_map<int, int> indexMap; for (int i = 0; i < inorder.size(); ++i) { indexMap[inorder[i]] = i; } return build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1, indexMap); }

难点在于下标边界极其容易算错：左子树的preorder区间和中序区间长度必须相等，这是很容易被忽视的关键。我的习惯是先用纸画出一个具体的例子，把每个区间的起止下标写出来，再写代码，不要凭空在脑子里推。

最近公共祖先（LCA）是另一类高频率题：

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (!root || root == p || root == q) return root; TreeNode* left = lowestCommonAncestor(root->left, p, q); TreeNode* right = lowestCommonAncestor(root->right, p, q); if (left && right) return root; return left ? left : right; }

这里的关键是理解递归返回的语义：如果子树里找到了p或q，就返回找到的节点；如果两边都找到，说明当前root就是LCA；如果只有一边找到，说明LCA在那一侧。这个设计比背代码重要得多，因为面试官会换着法考“如果节点保证存在”“如果节点不一定存在”等变体。

3.3 树题里的复杂度沟通

树相关题目的复杂度分析，几乎是每个面试官必问的。

时间复杂度通常是O(n)，因为每个节点访问一次；空间复杂度要分两点讲：迭代方法的额外空间取决于使用的数据结构，递归方法的空间复杂度等于递归深度，也就是树的高度。

关于树高，面试里要把最坏情况和平均情况区分开。一个退化成链的树，高度是O(n)；一棵平衡树，高度是O(logn)。我通常的表述是：“空间复杂度取决于树高，最坏情况下是O(n)，平衡情况下是O(logn)。”能主动说出最坏与平均的区别，会让面试官觉得你考虑问题比较全面。

4. 哈希与栈队列：语言细节与算法模型的结合

哈希表是大量高频题的“万能工具”，栈和队列则是很多经典算法模型的骨架。这一部分的面试题有个特点：既考算法思路，也考C++STL容器的底层机制，两个层面都要准备。

4.1 unordered_map的底层与自定义哈希

很多人用unordered_map用得飞起，但被问到底层机制就含糊了。常见问题包括：哈希冲突怎么解决（链地址法）、负载因子什么时候触发rehash（经验值通常是1.0）、为什么频繁插入删除时迭代器不会失效而vector会失效。

另外一个更实际的问题是：如果key是自定义结构体，怎么放到unordered_map里？默认情况下，编译会报错，因为std::hash没有针对你的类型定义特化版本。解决办法是两个：第一，给类型提供hash函数对象；第二，特化std::hash。

比如现在要用pair<int, int>做key，虽然标准库从某个版本开始提供了pair的hash，但在兼容考虑下我们常常自己写一个简单hash：

struct PairHash { size_t operator()(const pair<int, int>& p) const { return hash<int>()(p.first) ^ (hash<int>()(p.second) << 1); } }; unordered_map<pair<int, int>, int, PairHash> mp;

这里用“异或+移位”组合两个整数的哈希。为什么hash运算对unordered_map来说很重要？因为哈希函数的散列质量直接决定了冲突频率，冲突多了，查找退化成链表遍历，哈希表就失去了O(1)的优势。

4.2 单调栈：一类题三分钟找到思路

单调栈是面试中喜欢考但又很多人写不熟的模型。典型题包括“每日温度”“接雨水”“柱状图中最大的矩形”。

理解单调栈最好的方式是想清楚一个场景：股票曲线里找“下一个更大的价格”，需要顺序遍历，用栈维护一个递减序列，遇到比栈顶大的就出栈结算。

以每日温度为例，代码模板非常统一：

vector<int> dailyTemperatures(vector<int>& temperatures) { int n = temperatures.size(); vector<int> ans(n, 0); stack<int> stk; for (int i = 0; i < n; ++i) { while (!stk.empty() && temperatures[i] > temperatures[stk.top()]) { int prevIndex = stk.top(); stk.pop(); ans[prevIndex] = i - prevIndex; } stk.push(i); } return ans; }

两个细节值得注意：一是栈里存的是下标而不是温度值本身，因为我们需要计算索引距离；二是栈内保持的是从栈底到栈顶严格递减，遇到更大元素就弹栈结算，当前元素最终入栈，作为后续元素的“候选最近更大值”。这个“维护单调性+结算答案”的思维框架，套到其他题目里同样适用。

4.3 deque与滑动窗口

滑动窗口最大值这题，解决思路是用双端队列维护一个“有潜力的最大值候选序列”：

vector<int> maxSlidingWindow(vector<int>& nums, int k) { deque<int> dq; vector<int> result; for (int i = 0; i < nums.size(); ++i) { // 移除已经滑出窗口左端的下标 if (!dq.empty() && dq.front() == i - k) dq.pop_front(); // 维持从大到小的单调性 while (!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back(); dq.push_back(i); // 窗口形成后开始记录结果 if (i >= k - 1) result.push_back(nums[dq.front()]); } return result; }

为什么用deque而不是优先队列？因为滑动窗口需要同时从两端操作：队首弹出过期元素，队尾加入新元素并淘汰比新元素小的候选者。优先队列（堆）能快速取最大值，但要惰性删除过期元素，代码复杂度会上升。deque双端都能O(1)操作的优势在这里展露无遗。

5. 面试手撕代码的临场节奏与复盘方法

很多人的问题不是不会做题，而是现场发挥不出来。我面试别人时最常见的场景是：候选人拿到题，话不多说埋头就写，写到一半发现函数签名理解错了，或者边界条件没考虑就擦掉重来，代码丑且乱。这里分享几个应对临场手撕的实战经验。

5.1 先澄清输入输出，再讲思路，最后动笔

拿到题，先别急着写。问几个问题：

• 如果输入为空，期望返回什么？
• 如果存在重复元素，是否需要处理？处理规则是什么？
• 能否修改原数组/链表，还是必须生成新结构？
• 数据规模大概多大，是否能容忍O(n²)复杂度？

我的习惯是把下面三句话在脑海里过一遍再说给面试官：

“我打算用XX数据结构，因为它的XX操作是O(1)。然后核心思路是……，边界情况这里的处理办法是……。最后我会跑一个具体例子验证。”

这段表达的妙处在于，它同时展现了三个能力：数据结构选型意识、边界思维、测试意识。即使最后代码有一点瑕疵，沟通环节已经为面试官留下了较好的印象。

5.2 写代码过程中的三个习惯

第一，变量名尽量语义化。cur、prev、slow、fast这类命名比a、b、c清晰得多，面试官看的时候也能跟上思路。

第二，循环里保持循环不变量清晰。比如二分查找，while (left < right)和while (left <= right)的选择，本质是“维护的区间是左闭右开还是左闭右闭”。如果心中没有这套约束，边界条件就约等于靠猜。

第三，写完代码一定手动跑一个用例。不用太长，两三个节点或五六个数就行。手动模拟的过程中很容易发现差一错误、方向写反的bug。这种检查习惯在真实开发里也很有用，能省下大量调试时间。

5.3 复盘比刷量更重要

刷题数量多不等于面试稳。我自己的做法是，每道题做完了之后，都会在笔记里记下几个字段：题目的考点（链表？DP？回溯？）、核心数据结构、关键边界条件、最坏复杂度、我当时卡住的地方。

整理到一个阶段后，自然形成了一套自己的模板库。比方说：

• 链表类模板：哨兵节点+快慢指针
• 区间重叠类模板：按起点排序+扫描维护当前区间
• 排列组合类模板：回溯+剪枝
• TopK类模板：堆或快速选择

这些模板不是背诵，而是对一类题思维方式的提炼。面试时看到题，先归类，再套模板，效率会高很多。

我个人实际测试下来，用“手动跑测试用例+整理分类模板”这两件事，比多刷200道新题带来更大的面试提升。顺便说一句，平时练习时不要总依赖IDE的断点调试，多试试在白板上手写，或者在一个没有自动补全的环境里写，面试现场往往就是这种条件。这种“裸写”能力，只能靠平时多练。