C++后端面试算法题第十期：五道高频易错题全解析-平芜编程栈

第十期打卡来了。C++后端面试算法题这个系列，到了这一期已经攒下不少素材。前九期把链表、二叉树、哈希、动态规划这些方向轮着刷了一遍，这期我没打算继续堆难题，反而挑了五道“高频、易错、可深挖”的题目：合并两个有序链表、无重复字符的最长子串、LRU缓存、二叉树最近公共祖先、买卖股票的最佳时机。它们不是最高深的题，却是很多后端候选人在笔试里丢分、在面试问答里被追问到卡壳的题。

后端岗位做题为什么绕不开这几道？因为后端工作几乎每天都在和数据批量打交道。接口要限流，缓存要淘汰，有序数据要合并，树形结构要做权限或组织映射。面试官挑这些题目，不是说只让你背出代码，而是想通过短短二十分钟看出几件事：能不能把题目条件读清楚，能不能把边界情况想完整，能不能在压力下稳定写出可运行的C++代码。C++候选人还要额外回答一个问题：你平时用STL顺得很，底层原理清不清楚？

所以第十期按三条标准选材：第一，大厂后端笔试面试高频；第二，每种题都能延伸到一个实际工程场景；第三，适合用C++实现，能把语言细节展示出来。刷完这五道题，建议再按“一题三问”的方式复盘一遍，效果会比单纯刷量好很多。

1. 第十期选题思路：为什么又把这几类题翻出来刷

这一期不是随便挑五道题凑数。后端面试的算法题库非常庞大，难度也深不见底，但高频题永远是那么一批。它们的共同特征是：代码量不大，边界条件多，可以往多个方向追问。恰好适合考察一个C++候选人的数据结构功底、编码习惯和沟通能力。

我见过不少候选人，难题刷了一堆，结果在一道简单链表题上栽了跟头。原因往往不是不会，而是忽略了输入为空的情况，或者while循环里指针移动的次序不对。这类错误在笔试中非常致命，因为线上答题没有断点调试，错了就是错了。而大厂面试官又尤其喜欢用这种“不难但容易错”的题做筛选，因为它能迅速暴露一个人的基本功。

1.1 五道题背后的考点分布

先给一张总览表，方便你判断自己哪块薄弱，后面每道题再单独展开。

题目	核心考点	后端场景对应
合并两个有序链表	链表、哨兵节点、迭代与递归	有序队列合并、归并排序思想
无重复字符的最长子串	滑动窗口、哈希表、数组计数	接口限流、日志窗口统计
LRU缓存	哈希表 + 双向链表、O(1)操作	本地缓存、缓存淘汰策略
二叉树最近公共祖先	二叉树遍历、递归返回值设计	权限树、评论楼层祖先查找
买卖股票的最佳时机	动态规划、状态压缩	收益计算、订单状态机

这五题覆盖数组、字符串、链表、二叉树、动态规划五个方向。链表题检查指针操作，滑动窗口题检查双指针意识，LRU检查数据结构选型和容器能力，LCA检查递归拆分，股票题检查状态定义。可以说一份稍微全面一点的后端算法考察，基本就围绕这些能力展开。

为什么强调“基础”？因为这五道题的代码量都不大，特别适合在面试里手写。面试官能在很短时间里看到你整个思考过程：写之前问不问题、写的时候注释清不清楚、写完会不会主动测边界。所谓“大厂必刷”，未必是难题海，而是这些基础题最能暴露真实水平。

1.2 代码环境与约定说明

本期代码按 C++11/14 标准书写，用到的头文件都在代码块里给出了。你在本地编译器上直接建一个空项目，把每个函数粘贴进去就能编译。下面几条是我自己长期刷题总结的约定。

提示：面试刷题环境往往不允许联网，所以代码应当只依赖标准库，不要依赖在线工具或第三方库。养成纯手写习惯，关键时刻才稳。

我写代码有三个固定习惯。第一，先确认输入是否可能为空：链表可能是空指针，字符串可能是空串，数组可能是空数组。第二，写完立刻口头算一遍复杂度，尤其是空间复杂度，“额外空间”这几个字要常挂嘴边。第三，想清楚返回值语义，再看看是否需要特殊处理退化输入。这三个习惯能覆盖大多数面试题的失分点。

代码中大量使用using namespace std，这是为了方便展示。如果你在工程代码里也这样写，会让命名空间污染变严重，面试官问到这个问题时你可以直接答出来。另外，所有接口命名和参数顺序尽量贴近常见在线评判系统的风格，方便你提交到OJ时直接复用。

2. 五道高频题完整拆解：思路、代码与复杂度

这一章是整篇博文的正文核心。每道题我按一个统一节奏展开：题干、思路、代码、复杂度、面试追问。你可以直接照着练习，也可以把某个题单独摘出去做复习卡。

2.1 合并两个有序链表：别让指针在边界处迷路

题目描述：给定两个升序链表，返回合并后的升序链表。要求原地调整节点的next指针，不创建新节点。

看起来是链表题里最简单的一道，但我见过太多人在这里翻车。最容易出问题的地方有三个：递归版本在长链表上栈溢出；迭代版本忘了处理某个链表已走完的情况；while循环里tail指针的移动位置写错，导致死循环或丢失节点。

思路：用哨兵节点 + 迭代。哨兵节点是一个不参与实际业务的哑节点，作用是不用单独判断“合并后链表为空”的情况。定义一个dummy，让tail始终指向当前结果链表的最后一个节点。循环比较两个链表的头节点值，谁小就把谁接在tail后面，然后移动对应链表的指针，最后tail向后走一步。

循环退出后，最多有一个链表还剩节点。这里很多人会写“再写一个while把剩余节点逐个接上”，其实没必要，直接让tail->next指向不为空的链表头就可以了。因为原链表本身就是有序的，剩余节点整体接到后面依然是升序。

代码实现：

struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* tail = &dummy; while (l1 != nullptr && l2 != nullptr) { if (l1->val <= l2->val) { tail->next = l1; l1 = l1->next; } else { tail->next = l2; l2 = l2->next; } tail = tail->next; } tail->next = (l1 != nullptr) ? l1 : l2; return dummy.next; }

复杂度分析：时间 O(n + m)，n 和 m 分别为两个链表长度；空间 O(1)，因为只用了常数个辅助指针。如果写递归版，时间同样是 O(n + m)，但递归调用栈会到 O(n + m)，当链表很长时可能栈溢出。

面试官扩展问法：把两个链表改成 K 个有序链表。如果逐个两两合并，复杂度会变成 O(K²N) 或者 O(KN)，取决于合并顺序。建议答案分两层：第一层，把所有链表头放进最小堆，每次取堆顶节点接到结果末尾，再把该节点的后驱入堆，复杂度 O(N log K)，N 为所有链表节点总数；第二层，也可以两两归并，复杂度同样是 O(N log K)，但常数和写法不同。这一问能直接看出候选人有没有真正理解归并思想，建议认真练一次最小堆版本。

2.2 无重复字符的最长子串：滑动窗口右边界不能着急往前跑

题目描述：给定一个字符串 s，找到其中不含有重复字符的最长子串的长度。例如s = "abcabcbb"，结果是 3，最长子串是"abc"。

暴力思路是枚举所有子串，再用哈希判断是否有重复，复杂度 O(n²)，写起来简单，面试却丢分。合格的解法是滑动窗口，一次遍历搞定。

思路：用两个下标left和right框住一个窗口，窗口内的子串始终保持无重复字符。right每向右扩展一位，就检查新字符是否在窗口内已经出现过。如果出现过，把left跳到重复字符上次出现位置的下一个下标，同时更新该字符的最新位置，最后计算窗口长度，更新答案。

关键是“怎么判断字符出现过”。我推荐用固定长度数组vector<int> pos(256, -1)，下标是字符的ASCII码，值是它最近一次出现的下标。数组访问 O(1)，比unordered_map常数小。字符串若包含高位字节字符，直接拿char做下标可能变成负数，必须通过(unsigned char)转换。

代码实现：

#include <string> #include <vector> #include <algorithm> using namespace std; int lengthOfLongestSubstring(string s) { vector<int> pos(256, -1); int left = 0; int ans = 0; for (int right = 0; right < static_cast<int>(s.size()); ++right) { unsigned char ch = static_cast<unsigned char>(s[right]); if (pos[ch] >= left) { left = pos[ch] + 1; } pos[ch] = right; ans = max(ans, right - left + 1); } return ans; }

复杂度分析：时间 O(n)，left和right各扫描一遍字符，总体线性；空间 O(1)，因为辅助数组大小固定为 256。

考题延伸：面试官如果让你手推"pwwkew"，可以直接在白板上画。我当时的推法是：right 到第二个 w 时，发现 w 上一次位置是 1，当前 left 是 0，所以窗口内已经有 w，left 跳到 2；这时窗口变成"wke"，长度更新成 3。手感极其重要，纸上多推几遍能避免代码把 left 更新错了。再延伸一步，这道题和后端接口限流非常像：限流窗口也是用左右边界记录时间区间，只是存的值从字符位置变成时间戳。能讲出这个联系，面试官会认为你有业务迁移能力。

2.3 LRU缓存：哈希表与双向链表的一对一配合

题目描述：设计一个LRU缓存，支持get(key)和put(key, value)，要求平均时间复杂度都是 O(1)。缓存容量固定，满了之后淘汰最近最少使用的键值对。

LRU是后端高频题里最有工程味道的一道。缓存系统、进程页面置换、本地缓存淘汰，核心全是LRU思想。为什么答案结构是哈希表 + 双向链表？因为get要按key快速查找，哈希表 O(1)；链表维护“最近使用顺序”，方便删除尾部最久未使用节点。但单链表删除任意节点需要从头找前驱，做不到 O(1)，所以必须用双向链表。

思路：标准做法是用list<pair<int, int>>保存key-value和最近使用顺序，链头表示刚访问过的，链尾表示最久未使用。另用unordered_map<int, list<pair<int, int>>::iterator>保存key到链表节点的映射。get命中时，把节点用splice移到链头，再返回值；put时先查是否存在，存在则更新值并移到链头，不存在则先判断容量，满了就把链尾节点删除，并从哈希表里删掉对应key，最后在链头插入新节点并建立映射。

list::splice是本题关键API，它能把节点从链表任意位置移动到指定位置，并且复杂度 O(1)，因为双向链表节点转移不涉及遍历。很多候选人不知道这个接口，选择自己手写双链表，那也没问题，但对指针失效的把握要求更高。

代码实现：

#include <list> #include <unordered_map> #include <utility> using namespace std; class LRUCache { public: LRUCache(int capacity) : cap_(capacity) {} int get(int key) { auto it = mp_.find(key); if (it == mp_.end()) { return -1; } int value = it->second->second; cache_.splice(cache_.begin(), cache_, it->second); return value; } void put(int key, int value) { auto it = mp_.find(key); if (it != mp_.end()) { it->second->second = value; cache_.splice(cache_.begin(), cache_, it->second); return; } if (cache_.size() == static_cast<size_t>(cap_)) { int oldKey = cache_.back().first; cache_.pop_back(); mp_.erase(oldKey); } cache_.emplace_front(key, value); mp_[key] = cache_.begin(); } private: int cap_; list<pair<int, int>> cache_; unordered_map<int, list<pair<int, int>>::iterator> mp_; };

为什么不建议用时间戳 + 排序？如果每次get都更新时间戳，淘汰时遍历所有key找最老时间戳，复杂度 O(n)；如果用堆维护时间戳，又需要处理节点更新时堆内元素的删除，工程上非常麻烦。双向链表的顺序天然就是访问顺序，这是数据结构选择的典范。

面试深挖方向：多线程场景怎么办？最简单的回答是给get和put加同一把互斥锁，正确性有保障但并发低；更好的回答是分段锁或者分片缓存，每个分片独立带锁，降低竞争；还可以说读多写少时考虑读写锁。这些问题没有标准答案，关键要表达你能从“正确性”和“吞吐量”两个维度权衡。实际工程里还要考虑链表节点内存分配开销，以及哈希表扩容时的停顿，能把这些提出来会更加分。

一个容易踩的坑：删除尾部缓存时，只操作链表却忘了mp_.erase(oldKey)。这样get老key依然能命中，而且内存不会真正释放，表现成“缓存命中率正常但内存持续上涨”。我早期调这个题就踩过，排查半天才发现哈希表里残留了陈旧键。这类一致性问题是后端工程师特别应该警惕的。

2.4 二叉树最近公共祖先：递归返回值设计的艺术

题目描述：给定一棵二叉树的根节点root和树中的两个节点p、q，返回它们的最近公共祖先。一个节点也可以是它自己的祖先。

这道题的递归代码极短，但要想明白“函数返回什么”才能稳。很多初学者一上来就想找路径，把祖先路径存下来再比较。那当然也能解，但代码长、时间空间都是 O(n)。这里我讲标准后序递归写法。

思路：对当前节点root，先处理空值：如果root为空或者等于p或q，直接返回root。如果不是，递归去左右子树找答案。拿到left和right两个返回值后，分情况判断：

如果left和right都不为空，说明p和q分别落在root的左右两侧，root就是最近公共祖先。
如果只有一侧非空，说明两个节点都在这一侧，直接返回这一侧的递归结果。
如果两侧都为空，这个分支没有目标节点，返回空。

这种自底向上的处理方法，本质上和动态规划的“先解决子问题，再合并结果”一致。返回值的含义必须统一：表示“子树内是否找到了 p 或 q，以及找到时的最近公共祖先候选”，这样递归才能一层层把信息传上去。

代码实现：

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

复杂度分析：时间 O(n)，每个节点最多访问一次；空间主要看递归栈深度，最坏退化成链表时 O(n)，平衡树时 O(log n)。所以严格说这个解额外空间不是 O(1)，如果面试官问“能否 O(1)”，需要换迭代法或父指针。

面试沟通注意：题目默认 p、q 一定在树里，但你不妨主动确认。如果 p/q 可能不存在，递归返回的语义会变复杂，需要用一个计数变量记录找到了几个目标节点。这个主动提问能体现严谨性。我见过面评里专门写“候选人主动澄清条件，加分”，可见细节真的重要。

扩展关联：如果把树换成二叉搜索树，LCA可以利用val大小关系剪枝。当前节点大于p、q则向左走，小于p、q则向右走，否则当前节点就是LCA，复杂度 O(高度)。这是同一问题在不同数据形态下的最优解，建议把两个版本都练一下。

2.5 买卖股票的最佳时机：从“状态定义”看懂动态规划

题目描述：给定一个数组prices，prices[i]表示第 i 天的股票价格。最多只能完成一笔交易，也就是只能买入一次、卖出一次，求最大利润。如果不能获利，返回 0。

很多人一看到动态规划就紧张，但这道题是理解“状态压缩”最好的入门例子。直接背“记录最小值，遍历更新答案”这种操作不是不行，只是面试官多问两句你就会露怯。我建议用状态语言理解它。

思路：设第 i 天卖出的最大利润是dp[i]。第 i 天卖出，必然是在 0 到 i-1 天中价格最低的那天买入。所以我们只要维护一个min_price，表示当前已扫描天里的最低价格，然后每天用prices[i] - min_price更新答案。因为答案只与“当前最低买入价”和“当前价格”有关，不需要存下全部dp数组，一个变量就够，这就是状态压缩。

为什么叫动态规划而不是贪心？因为每一步的最优值都依赖前面保存的最优状态（历史最低价），并且我们在每次决策时试图构造当前状态的最优解。贪心一般不保留状态，这里的min_price其实是一个被压缩的“状态”。

代码实现：

#include <vector> #include <algorithm> using namespace std; int maxProfit(vector<int>& prices) { if (prices.empty()) { return 0; } int min_price = prices[0]; int ans = 0; for (size_t i = 1; i < prices.size(); ++i) { ans = max(ans, prices[i] - min_price); min_price = min(min_price, prices[i]); } return ans; }

复杂度分析：时间 O(n)，空间 O(1)。这是最优解，面试时不用再纠结能降到 O(1) 以下。

扩展版本：面试官大概率会接着问“如果可以无限交易，但任何时候最多持有一股，怎么算”？这时候要定义两个状态：hold表示当前持有股票的最大收益，cash表示当前不持有股票的最大收益。每天做一次状态转移，最终答案就是 cash。这样你能顺着拓展到带冷却期、带手续费、最多K笔交易。学了状态机，再遇到“订单状态如何流转”这类业务题，思路会打开很多。

还有一个不起眼但重要的点：当价格始终递减时，答案必须是 0，而不是负数。代码初始化ans = 0正好解决了这个语义。很多人只测上涨样例，忘了递减样例，导致把答案算成负数，这种测试疏漏在面试里非常扣分。

3. 刷题常见的坑：边界、迭代器与口误

前面是五道题的正解，这一章是我从模拟面试和日常调代码里总结出来的常见问题。算法能力差不多的情况下，细节处理直接决定面评档次。

3.1 边界条件自查清单

很多代码在正常用例上跑得很好，一到边界就崩。我列了一张表，建议每道题写完都按这个测一遍。

题目	必测边界	常见翻车点
合并两个有序链表	两链表都为空、其中一个为空	while里直接解引用空指针
无重复字符的最长子串	空串、全相同字符、长度1	left更新错误导致窗口越界
LRU缓存	容量为1、重复key、get不存在key	删除尾部后忘了同步哈希表
二叉树最近公共祖先	单节点、p是q祖先	返回值处理混乱
买卖股票	空数组、全下降序列	数组越界或返回负数

我写代码的方法是：提交前先用三条用例跑一遍。第一条是普通用例，第二条是空输入，第三条是退化输入。比如合并链表测l1 = nullptr, l2 = 单节点；滑动窗口测空串；LRU测容量1时连续put两个key。这三条跑通，基本能避免大量低级失分。

3.2 迭代器失效与容器操作陷阱

C++ 和很多语言不同，容器修改后迭代器可能失效。LRU 的splice和emplace_front都在改链表结构，但list的节点转移不会让其他迭代器失效，所以保存的mp_映射依然有效。真正要小心的是unordered_map的 rehash：插入元素可能触发扩容，使之前的迭代器全部失效。好在put里我们先查在不在，查到后修改并移动节点，不插入新元素；只有新增键时才emplace_front并给mp_赋值，这个顺序能避开迭代器失效问题。

另一个常见错误是在循环遍历 vector 或 map 时做删除操作。后台处理定时任务时，很多人会写“遍历集合，找到超时项，然后 erase”，结果在 for 循环里 erase 迭代器导致后续迭代器失效。正确姿势是先用remove_if或先收集要删除的 key，循环结束后统一清理。这个点在后端开发里几乎天天见到，能在算法题里顺手点出来，面试官会更信任你的工程经验。

3.3 面试表达里的三个禁忌

第一个禁忌：把“时间复杂度 O(1)”挂在嘴边，却没解释常数因子。LRU 的 get 确实 O(1)，但哈希查找 + 链表拼接各有代价。第二个禁忌：把空间复杂度说成 O(1)，递归实现明明要占调用栈。第三个禁忌：代码写完不说话。正确做法是写完主动说“我来分析一下复杂度”，然后简明讲两句。尤其是递归、滑动窗口这类题目，不说思路直接写，面试官很可能认为你在背题。

我见过一位候选人，五道题里三道默写正确，但面试官问他“为什么会想到用双向链表”时，他沉默了二十秒才挤出“因为这是标准答案”。这就是典型的会背不会讲。所以本博文每一道题都写了“为什么”，不只是给代码。

4. 怎么把题目变成面试里的实际加分项

刷题容易陷入“刷过就忘”，因为缺少沉淀。这里分享我自己的复盘方法：把每题做成可复述的知识点，再和工程场景绑定，最后放进一个可复用的答题模板里。

4.1 一题多解：面试时的选择策略

同一道题有多种解法时，面试时不必都写完，但要能回答“为什么选这个解法”。合并有序链表，迭代空间 O(1) 但代码长，递归空间 O(n) 但代码短，我优先写迭代，因为后端线上环境对栈敏感；如果题目明确限制递归深度，迭代就是唯一选择。

滑动窗口里，unordered_map更通用，数组更高效。我会先写数组方案，并说明字符集前提，再说可以改 map 支持任意字符集。这样既展示了效率意识，又展示了灵活性。买股票那题我会先写扫描版，再补一句“它本质是压缩后的动态规划”，然后顺势展开状态定义。这套节奏能让面试官觉得你是在讲题，不是背答案。

4.2 从算法题延伸到后端工程场景

后端候选人最容易忽略的是“算法结论如何落地”。LRU 是最典型的可扩展题。你可以说：线上本地缓存一般会加锁，简单做法是全量互斥锁，性能不好；高并发下用分片，或者引入外部缓存组件，再或者允许统计误差时用抽样淘汰。这句话不需要背一堆名词，只需要把权衡逻辑讲清楚。

滑动窗口那题也能延展：接口限流统计一分钟内请求次数，本质是滑动窗口计数；日志系统统计某个时间段内的独立用户数，也是滑动窗口去重。差异只在于窗口里存的是下标还是时间桶。能说出这个抽象，比背“滑动窗口模板”有用得多。

二叉树 LCA 可以延展到权限树：找到两个角色的最近共同上级组织，或者评论区的最近共同楼层。只要存储结构是树，LCA 的查找思路完全一致。我把这种迁移过程称为“把算法题升华成方案题”。面试官问“你项目里用过哪些数据结构”时，你可以直接拿这些场景举例。

4.3 如果时间不多，按这个顺序练

这期五道题如果只想抽半天，我的推荐顺序：前20分钟默写合并链表两种写法，重点练迭代；再花30分钟手推滑动窗口状态变化，写无重复字符子串；然后花1个小时做LRU，必须测容量为1的用例；接着用画图方式跑二叉树LCA，把每个递归返回值标在图上；最后把股票题改成“允许无限交易”，对比两版状态定义。

按我自己的经验，单刷一道题收益有限，一题三问才是提高效率的关键。所谓三问就是三道自问：能不能换一种解法？能不能优化复杂度？改一个条件后会怎么变？LRU问并发，滑动窗口问超长字符，二叉树问换成二叉搜索树。做20道题，不如把这5道题每个方向吃透。

5. 综合练习：五道题拼出一个后端小系统

如果你觉得每道题都单独刷没意思，我建议做一个组合练习：设计一个简单的“商品报价系统”，把五道题全部用上。这不是真实的商业项目，却是很好的面试训练场景。

5.1 场景设计：商品报价与用户访问服务

假设有一个商品系统，每天接收多个来源的报价数据，每个来源的数据都已经按价格升序排列。合并多个有序报价列表，就是“合并K个有序链表”的场景。系统还要记录用户最近浏览过的商品，容量有限，超出就淘汰最久没看的记录，这就是LRU。用户访问商品详情页时，后端要做限流，防止单个用户短时间刷爆接口，这里可以用滑动窗口思路统计访问次数。商品分类是一棵分类树，两个商品所属分类的最近公共分类就是LCA。最后，系统展示某商品历史价格走势，给用户计算如果昨天买今天卖最多能赚多少，这就是股票买卖问题。

把五道题放到同一个业务故事里，你会发现自己对题目的理解立刻不一样了。每个数据结构都不是孤立存在的，而是为了满足某个需求而被选择。面试官如果真的问“这道题在你的项目里有什么用”，你也能直接讲出至少一个完整场景。

5.2 综合回答的组织模板

我在模拟面试里常用一个三段式模板，分享出来供参考。第一步，拆需求：先说明这个场景里需要哪些核心操作，比如“缓存要支持O(1)的读和写，需要淘汰最久未使用”。第二步，选结构：结合需求说清楚为什么选哈希表+双向链表，而不是别的。第三步，谈边界：说明容量满了怎么做、get不到key怎么办、并发访问怎么保证一致。

这套模板适用于绝大多数算法面试题。你不需要背话术，而是要养成“需求—数据结构—边界”的思维惯性。很多候选人答不好题，不是因为不会写代码，而是因为不知道从哪个角度开始讲。有一个固定框架，至少不会语无伦次。