简介一份C版《剑指Offer》编程面试题源码包面向备战算法笔试和技术面试的开发者覆盖知名互联网公司面试中常见的经典题目用于系统梳理解题思路与代码实现细节。源码主题包括数组、链表、树、栈与队列、动态规划、递归、字符串匹配、排序搜索、设计模式、STL容器与智能指针、内存管理、面向对象、异常处理及模板与泛型编程等方面从基础数据结构到经典算法均有对应实现也便于按章节逐题对照书中讲解进行学习。压缩包共2098个文件约44.2MB核心为242个cpp与226个h源代码文件另含71个vcxproj、104个vcproj、5个sln等Visual Studio工程配置以及pdb、obj、tlog等编译调试产物打开对应工程即可查看代码与运行效果。目前已有373人学习下载适合需要系统刷题并通过实际编译调试来巩固C能力的读者。1. 剑指offer源代码C面试手写代码为什么还得靠它刷算法题这件事每年都有新人问“剑指offer过时了吗”但等到真坐在面试官对面被要求在白板上手写链表反转或者二叉树遍历时大部分人还是会回来翻这套题的C实现。原因很简单这套题考察的是最基础、最高频的数据结构与算法操作而C又偏偏是面试中最考验内存和指针功底的语言——你用Python写反转链表可能三行搞定但用C写就要面对空指针、断链、内存泄漏这些真实存在的问题。与其说剑指offer的源代码C版本是一份题解不如说是一套“面试手写代码的肌肉记忆训练”。它适合两类人一类是准备算法面试的C从业者需要把链表、二叉树、栈队列这些基础操作练成条件反射另一类是工作多年、平时写业务代码多但手写代码生疏的熟手想用最短时间把核心模板捡回来。这篇笔记就沿着“源码骨架怎么写、高频题怎么拆、OJ怎么过、坑怎么避”的顺序把值得落地的部分一次讲透。2. 剑指offer源码的骨架数据结构定义与C模板预写2.1 链表与二叉树结构体先把手写模板固定下来剑指offer的题目里链表和二叉树占了相当大的比重。很多人在刷题时栽在同一个地方题目看懂了解法也想明白了结果结构体定义写错或者构造函数没写导致编译器报错浪费时间。实际上这套题库里的链表节点和二叉树节点定义是非常固定的我一般会在刷题前就把这两个结构体背熟并固定成模板。// 单链表节点定义 struct ListNode { int val; ListNode *next; // 带默认值的构造函数方便直接 new ListNode(x) explicit ListNode(int x) : val(x), next(nullptr) {} };构造函数这里有个细节explicit关键字在力扣这类 OJ 上加了不会报错但能防止隐式转换带来的意外问题。next(nullptr)是 C11 以后的推荐写法不要用NULL或者0因为nullptr是真正的空指针类型重载函数时不会产生二义性。// 二叉树节点定义剑指offer中常写作 BinaryTreeNode struct TreeNode { int value; TreeNode *left; TreeNode *right; explicit TreeNode(int v 0) : value(v), left(nullptr), right(nullptr) {} };我给二叉树结构体加了默认参数int v 0好处是在写测试用例时可以new TreeNode()直接创建一个未指定数值的节点省去每次传参的麻烦。注意这里left和right的初始化顺序必须按照结构体内声明的顺序虽然构造列表里写成left(v), right(v)也没有关系但一定要养成按声明顺序初始化的习惯否则某些编译器开启-Wreorder后会有警告。固定好这两个结构体之后所有涉及链表和二叉树的题目都能直接复用不需要每道题重新定义。还有一点这里用struct而不是class是因为默认成员公有刷题时可以少写public:。2.2 标准库取舍vector、stack、unordered_map 的使用边界剑指offer里有一类题理论上要求你用自定义数据结构实现但实际上 OJ 是允许使用标准库的。这里的取舍原则我一般是这样定的题目考察的本质是“手动管理逻辑”就尽量不用库容器题目考察的是“算法思想”标准库可以大胆用。举几个高频例子用两个栈实现队列这个题在剑指offer里出现在“栈与队列”章节核心考点就是栈的语义如果用std::stack完全没有问题甚至更贴近工程实践而涉及排序算法时如果题目没有明确要求手写快排那么std::sort就能过但面试手写时还是建议自己实现一遍因为在白板上写sort(v.begin(), v.end())会给面试官留下“只会调库”的印象。另一个常见场景是哈希表。剑指offer的“复杂链表的复制”这道题可以用unordered_map建立原节点到新节点的映射很方便。但如果你在面试时使用最好补充一句“基于哈希表做映射时间O(n)空间O(n)”让面试官知道你清楚代价。标准库不是不能用而是要知道代价。#include unordered_map class Solution { public: Node* copyRandomList(Node* head) { if (!head) return nullptr; unordered_mapNode*, Node* map; Node* cur head; while (cur) { map[cur] new Node(cur-val); // 先复制所有节点 cur cur-next; } cur head; while (cur) { map[cur]-next map[cur-next]; // 用映射关系串联 map[cur]-random map[cur-random]; cur cur-next; } return map[head]; } };这段代码的逻辑分为两步第一次遍历只创建新节点并建立新旧映射第二次遍历再处理next和random指针。第一个while完不成指针串联因为当前节点的next可能还未创建这是链表复制类题目最容易漏的一点。参数上需要注意map[cur]如果当前节点不存在会插入默认值所以在第一个循环之前最好确保head不为空否则map[nullptr]会产生一个无意义的键值对。2.3 头文件与宏开关C源码的预编译防坑刷题时经常碰到一个问题本地编译运行好好的粘到 OJ 上报错“未定义标识符”。大多数情况下是因为头文件缺失或者命名空间问题。剑指offer早期的例题代码很多是单文件风格把#include堆在最上方但到了力扣这类平台标准库头文件不会自动帮你包含所以一个稳定的预编译模板很重要。#pragma once #include iostream #include vector #include stack #include queue #include unordered_map using std::vector; using std::stack; using std::queue; using std::unordered_map; using std::cout; using std::endl;有些人习惯直接写using namespace std;刷题时确实省事但在大中型项目中这是不推荐的容易引发命名冲突。我个人的折中方案是本地刷题可以用using namespace std加快速度但在提交到 OJ 或写正式源码时改为using std::vector;这种显式声明。还有一个实操技巧用宏开关控制调试输出避免写完整段代码后回头删打印语句。#define DEBUG #ifdef DEBUG #define LOG(x) cout x endl #else #define LOG(x) // 编译为空操作 #endif这个宏的作用是本地调试时LOG(val)会输出内容提交到 OJ 时只需把#define DEBUG注释掉所有打印语句自动失效。不这样做的话大部分人会在最后提交前一行行删cout错过截止时间。这里的参数说明很简单LOG宏只接受单个表达式如果需要打印多个变量写成LOG(a b)也可以因为cout的流式操作本来就支持链式。3. 高频题型C源码拆解链表、二叉树、栈队列这样写3.1 链表题反转链表的三指针迭代法为什么不会断链反转链表是剑指offer里出现频率极高的一道题也是很多新手第一次体会到“指针顺序不对就翻车”的题目。网上流传的解法有递归和迭代两种我建议面试时首选迭代因为递归虽然代码短但对栈深度的解释成本更高。迭代法的核心是三指针prev指向当前节点的前一个节点curr指向当前处理节点nextTemp临时保存后继节点。class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; ListNode* curr head; while (curr) { ListNode* nextTemp curr-next; // 1. 保存后继防止断链 curr-next prev; // 2. 当前节点指向前驱 prev curr; // 3. prev 前移 curr nextTemp; // 4. curr 前移 } return prev; } };这段代码的四个步骤顺序绝对不能换第 2 步执行之前nextTemp必须先保存curr-next否则一旦把curr-next改成指向prev原来的后继就找不回来了。最后的返回值是prev而不是curr因为在循环结束时curr已经为空prev恰好指向原链表的末尾节点也就是新链表的头节点。参数上需要注意当head为空链表时while循环不会执行函数直接返回nullptr这正好符合预期。很多人在这个简单用例上以为不会出问题但面试时一旦在边界用例上翻车印象分损失会很大。如果面试官让你优化可以考虑用递归写法做对照但不要主动先说留给对方追问。3.2 二叉树题重建二叉树时前序与中序的边界计算重建二叉树是剑指offer里的经典难题给一个前序遍历和中序遍历还原整棵树。C实现里最容易出错的地方是两个边界一是中序遍历中找到根节点索引后左子树和右子树的区间怎么划分二是在递归调用时传入的 vector 切片是否越界。我见过不少人栽在这里就是因为vector的迭代器区间是左闭右开稍不留神就把下标算错。class Solution { public: TreeNode* buildTree(vectorint preorder, vectorint inorder) { return build(preorder, inorder); } private: TreeNode* build(vectorint preorder, vectorint inorder) { if (preorder.empty()) return nullptr; int rootVal preorder[0]; TreeNode* root new TreeNode(rootVal); int idx 0; while (inorder[idx] ! rootVal) idx; // 在中序中找根的位置 vectorint leftIn(inorder.begin(), inorder.begin() idx); vectorint rightIn(inorder.begin() idx 1, inorder.end()); vectorint leftPre(preorder.begin() 1, preorder.begin() 1 leftIn.size()); vectorint rightPre(preorder.begin() 1 leftIn.size(), preorder.end()); root-left build(leftPre, leftIn); root-right build(rightPre, rightIn); return root; } };这里的关键在于前序遍历的第一个元素一定是当前子树的根找到它在中序遍历中的位置idx后中序的[0, idx)区间属于左子树(idx, end)区间属于右子树。前序的划分则需要借助左子树节点数量leftIn.size()紧随根节点之后的leftIn.size()个元素属于左子树剩下的属于右子树。这个实现有个性能问题vector切片每次都要复制整段数据递归深度大时耗时很可观。更优的做法是传递两个 vector 的索引范围只复制引用不复制数据。我一般会把这种写法当作面试加分项面试官问“能否优化空间”时立刻切换过去代码逻辑不变只是把参数改成四对索引。3.3 栈队列题用两个栈实现队列的倒数据时机用两个栈实现队列是剑指offer里栈与队列章节的代表题目考察的是“栈先进后出、队列先进先出”的语义转换。核心思路是一个栈专门负责入队另一个栈专门负责出队。入队时直接压入stack1出队时如果stack2为空就把stack1的所有元素依次弹出并压入stack2最后从stack2顶部弹出。class CQueue { public: void appendTail(int value) { stack1.push(value); // 入队压入栈1 } int deleteHead() { if (stack2.empty()) { while (!stack1.empty()) { stack2.push(stack1.top()); stack1.pop(); } } if (stack2.empty()) return -1; // 两个栈都空队列无元素 int ret stack2.top(); stack2.pop(); return ret; } private: stackint stack1; stackint stack2; };这里最容易出错的是deleteHead最前面的判断如果stack2非空说明之前倒进去的元素还没出完此时不应从stack1再倒数据否则会打乱顺序。只有stack2完全为空时才能倒而且要把stack1里的全部元素一次性倒完。返回值设计上也值得注意剑指offer原题里队列为空时返回 -1但在某些平台变体里要求抛出异常或返回哨兵值。写代码时最好先确认平台的要求不要盲目复用这段逻辑。如果题目改成了“队尾插入、队首删除”支持多种操作那就把appendTail和deleteHead当作两个独立操作分别考虑不要在appendTail里提前倒数据。4. 从源码到OJ判题平台差异、调试方法与超时定位4.1 牛客网与力扣的类封装差异同一个题两套壳剑指offer的题目在不同 OJ 上的呈现方式差别挺大这是新手最容易蒙圈的地方。力扣一般把题目包装成一个Solution类让你实现指定的成员函数输入输出由系统处理牛客则更接近早期的 ACM 风格有的题需要自己写main函数读输入有的则封装好了类。同一个题在两端甚至可能出现函数名不一样的情况。我一般会在刷题前确认两件事第一平台要求的是“函数式提交”还是“完整程序提交”。函数式提交只需要实现核心逻辑代码里不能有main否则编译报错完整程序提交则需要自己处理输入格式。第二链表和二叉树节点的定义是否自带如果自带不要重复定义否则会报重定义错误。做法很简单本地维护一份剑指offer的C源码目录每个题一个.cpp文件文件里只写核心函数或类实现再单独建一个带main的测试文件用#include引入。这样切换平台时只需要改测试文件不需要动核心代码。4.2 自己搭最小测试台printf调试在多指针题里的妙用很多人调试链表二叉树题目时只用断点但断点调试在指针断了的情况下非常痛苦你看到的局部变量可能是一个非空的指针但访问它的next已经指向了非法地址。这种情况下打印反而是最快的定位方式。我一般会写一组固定的辅助函数放在每个文件的顶部用来输出链表和二叉树结构// 打印链表用于检查反转、删除等操作后的链表结构 void printList(ListNode* head) { while (head) { cout head-val - ; head head-next; } cout nullptr endl; } // 打印二叉树前序遍历用于检查重建、遍历是否正确 void printPreorder(TreeNode* root) { if (!root) { cout # ; return; } cout root-value ; printPreorder(root-left); printPreorder(root-right); }注意printPreorder的输出里把空节点打印成了#这个技巧能验证树的形状是否完整。如果你只打印值遇到空树时什么都没输出很难判断是树本身就是空的还是递归提前终止了。加了#之后重建二叉树的结果可以完整比对很方便。在代码里写调试打印时不要直接提交到 OJ。用前面提到的LOG宏控制或者写完定位后立刻删掉。另一个经验如果题目要求修改链表结构在改动前先打印一次原始链表改动后再打印一次用两次输出对比就能快速看出哪一步出了问题。4.3 超时排查的三个黄金点循环条件、递归终止与容器复制C刷题超时不像 Java 或 Python 那样常见但一旦超时问题往往比较深。我排查时固定按三个点来查效率很高。第一循环条件是不是永远为真。比如链表的遍历写成了while (node-next)而忘记了在循环体内移动指针这是死循环里最简单的一种。排查方法是在循环体内加一个计数器超过1000000次主动跳出并打印标志。第二递归有没有终止条件。重建二叉树、中序遍历递归实现时如果递归入口的判空写错位置就会出现无限递归。最典型的现象是函数一开始没有判断node是否为空而是在下一次调用时才判断这会导致某一次递归传入nullptr后进入函数访问node-val崩溃或者因为node-left始终指向自己而无限递归。// 错误示范没有在函数入口判空 void badTraversal(TreeNode* root) { cout root-value endl; // 空指针直接崩 badTraversal(root-left); badTraversal(root-right); }正确的做法一定是在函数入口第一行就判断if (!root) return;。这既是解题习惯也是工程习惯。第三容器复制是否产生了过高的复杂度。比如在循环里用vector的erase删除头部元素在数据量大时会退化成 O(n²)解决办法是改用双指针或者deque。5. C刷剑指offer的七个避坑记录5.1 空指针访问本地越界VS线上崩溃现象在本地调试时链表反转偶尔能跑出结果提交到 OJ 直接runtime error。原因输入包含空链表代码里没有判空就访问head-val。本地环境的内存布局碰巧让空指针访问没有立刻崩溃但 OJ 的检测机制更严格直接报错。解决在所有链表题的入口统一加一句判空。我习惯在拿到head后立刻写if (!head) return nullptr;不要等到用到的时候再判断因为多指针链式操作里任何一个中间指针为空都可能被忽略。5.2 倒数第K个节点K值越界的翻车现场现象测试用例里链表长度为 5求倒数第 6 个节点期望返回nullptr但代码返回了倒数第 1 个节点。原因很多解法是双指针快指针先走 K 步再和慢指针同步走。但代码没有判断快指针能否走完 K 步导致 K 越界时快指针已经到达末尾慢指针停在了错误的节点上。解决快指针出发后每走一步都检查是否为空。走到 K 步之前就遇到空指针直接返回nullptr不要等循环自然结束。ListNode* getKthFromEnd(ListNode* head, int k) { ListNode* fast head; for (int i 0; i k; i) { if (!fast) return nullptr; // k 大于链表长度提前终止 fast fast-next; } ListNode* slow head; while (fast) { slow slow-next; fast fast-next; } return slow; }这段代码特别适合用来给面试官讲边界思维循环里先判断fast是否存在再移动把越界风险卡在第一步。5.3 反转链表丢后继最常见的指针顺序错误现象反转链路到一半后半段整体消失了打印结果只输出了倒数第一个节点。原因执行curr-next prev之前没有把curr-next保存到临时变量。一旦指针转向原链表从这里断裂后面的节点全部丢失。解决无论如何都要在三指针迭代中维持“先保存、再转向、后移动”的顺序。具体顺序是nextTemp curr-next; curr-next prev; prev curr; curr nextTemp;这个顺序可以作为肌肉记忆背下来。5.4 递归深度过大导致栈溢出现象二叉树高度接近 1000 时递归版本的中序遍历在 OJ 上报错栈溢出但本地测试却通过了。原因默认栈空间在 OJ 上往往比本地小树退化成链表时递归深度等于节点数容易打爆栈。解决深度可能很大的题型改用显式栈迭代写法。以中序遍历为例用std::stack模拟递归过程虽然代码长一些但稳定不爆栈。如果是面试现场先写递归并说明“整体思路如此如果树深我可以用迭代”通常能获得更好评价。5.5 NULL与nullptr混用导致编译警告或错误现象一段代码在力扣里编译通过放到牛客的旧编译器上报错NULL was not declared in this scope。原因不同的编译器标准对NULL的支持不一致而nullptr是 C11 才引入的关键字。老平台如果默认标准较低可能不识别nullptr。解决把代码里的所有NULL统一改成 nullptr或return 0如果目标平台连nullptr都不支持考虑用#if __cplusplus 201103L宏做兼容不要手动在代码里写两套判断。5.6 结构体重复定义导致编译失败现象本地自己定义了TreeNode平台题目又自带TreeNode提交时报重定义。原因平台已经通过宏或者全局定义注入了树节点结构你再写一遍相当于重复定义同一个符号。解决提交到平台前注释掉结构体定义只保留核心算法代码。本地测试需要结构体可以新建一个my_define.h文件存放结构体用条件编译控制是否引入。5.7 忘记释放内存造成的内存泄漏现象运行结果正确但平台有内存检查时报memory leak。原因用了new创建链表节点或树节点后没有delete。OJ 内存泄漏有时不会直接判错但在某些严格环境中会扣分。解决刷题阶段我自己其实也很少主动释放全部节点但有一个习惯必须保留在代码里凡是new的对象如果是自己负责销毁就成对写delete。面试时可以主动提“实际工程中应该用智能指针避免手动释放”但白板题通常不需要真的释放让面试官知道你清楚这个点就够了。6. 源码的进阶打磨把一份会动的模板变成记忆里的肌肉反应刷完一轮剑指offer的C源码后接下来价值最大的事情不是刷第二遍而是把每个模板做一次“极限压缩”。以我自己的经验来说反转链表的迭代写法、两个栈实现队列、快慢指针找中点这些核心操作应该能在一分钟之内无思考默写完成达到不需要看注释就能写对的程度。检验方式很简单开一个空白文件随机抽十个高频题在纸上写代码写完不编译和标准答案比对。如果一次性通过的超过八成说明肌肉记忆已经形成否则就需要针对反复出错的题目做专项回炉。在这个过程中我会做一件平时刷题不太做的事给每个核心模板写两种风格。第一种是“面试版”要求代码足够短、变量名清晰、逻辑一步到位方便在面试官面前快速落笔。第二种是“工程版”加入智能指针、判空保护、异常处理更接近生产代码。这两种风格的差异本身就能帮助理解题目的本质——面试版考的是算法结构工程版考的是内存安全和可维护性。最后一个技巧值得单独说刷题时不要只盯着通过率。某开发者跟我说他能三分钟写完镜像二叉树但被问到“如果树特别深递归会不会爆栈”时愣住了。这说明算法代码背得熟但没有理解背后的计算资源代价。现在我养成的习惯是每道题写完以后强迫自己说一句“这个方案的时间复杂度是O(n)空间复杂度O(h)h是树高”说得出来就换下一题说不出来就回去看。一句话的总结比十遍默写更能建立底层认知希望帮到你。本文还有配套的精品资源点击获取