1. 为什么要自己手写链表而不用现成的容器1.1 面试场景下的造轮子考验链表是数据结构里最基础也最容易翻车的线性存储结构。我在带过几轮新人和实习生之后发现凡是简历上写着熟悉数据结构的聊到链表十有八九能说出std::list有自己的实现但真让对方在白板上写出一个不带头节点的单链表反转一大半人当场卡壳。这不是他们不会调库而是库用得太熟底层指针关系已经生疏了。这里说的手动实现单链表与双链表接口以及OJ挑战本质上不是要你重复造轮子而是要把指针的每一步变化练到肌肉记忆。实际面试里链表题往往以忽然反转判断成环合并两条有序链等形式出现背后考察的就是你能不能在不依赖任何容器的情况下自己把节点的前驱后继关系理顺。如果你能做到这一点面试官对你的基本功判断会高一个档次。从经验看链表题能一次写对的人写代码时的边界意识通常都很好这在我后面讲OJ挑战时会反复提到。1.2 手写链表的真实收益手写链表的第一个收益是真正理解内存和指针。像C里new出来的节点删掉时得自己delete忘记处理就会内存泄漏Python里对象引用计数看似自动但如果你只把节点交给容器去管很难体会到引用断开前后的代价。第二个收益是调试能力自己实现时崩溃点往往都在空指针和悬垂指针上你在这些地方摔过几跤之后以后看线上崩溃日志都会更有感觉。和数组相比链表最大的特点是插入删除不移动元素只需要改变前后节点的指针指向。但这种灵活性是有代价的随机访问是O(n)而且每个节点都要额外存指针空间开销比数组大。正是这些代价决定了什么时候该用链表、什么时候不该用。刷题时如果对这些没有意识很容易写出看着对、实际复杂度爆表的代码。2. 单链表结构定义与完整接口实现2.1 节点结构要不要带头节点单链表的核心概念其实很简单就是一个节点里存着数据和下一个节点的地址。C里最直接的节点定义是这样templatetypename T struct ListNode { T val; ListNode* next; ListNode(const T v) : val(v), next(nullptr) {} };但要动手封装一个可用的接口第一个关键选择就是到底带不带头节点。所谓头节点也叫哨兵节点是一个不存真实数据、专门用来辅助操作的节点。如果带头节点空列表也拥有一个固定入口插入删除时不用对head是否为空做特殊判断如果不用头节点空链表时head就是nullptr处理头插和头删时全得写if。我个人的建议是刷OJ时看清题目给的是哪种结构。绝大多数OJ输入都是不带头节点的真实链表直接用head指向第一个数据节点就行日常自己实现练手时两种都写一遍感受一下差异。带头节点的好处是代码能少一半if坏处是打印、遍历、求长度时都要跳过哨兵处理不好反而出错。2.2 核心增删查改接口一个单链表类的完整接口至少要包含size、empty、insert(index, val)、remove(index)、find(val)、print。其中最关键的操作是insert和remove因为它们的边界条件最多。先说插入。合法的index范围是[0, len]index等于0意味着在头部插入index等于len意味着在尾部插入。实现时最稳妥的做法是统一走找前驱节点的逻辑但index为0时没有前驱必须单独处理。很多新手在这段犯的典型错误就是把node-next和prev-next的更新顺序写反结果把原链表后半段弄丢。正确顺序永远是先让新节点的next指向后继再让前驱的next指向新节点。删除操作同样要处理index为0的情况。删除头节点时head head-next删除其他节点时找到待删除节点的前驱prev让prev-next指向cur-next然后delete cur。这里最容易忽略的是删除后长度len要减一以及如果删除的是最后一个节点外部持有的尾指针如果有要不要同步。查找操作就简单了从head开始沿着next遍历比较值和目标值时间复杂度是O(n)链表结构天然不支持二分。2.3 反转与环形检测两个高频操作单链表最经典的进阶操作是反转。最常见的是迭代法准备三个指针prev、cur、next每次先保存cur-next再让cur-next指向prev然后三个指针整体往后挪直到cur为空最后prev就是新链表头。这个操作的难点不在于看懂而在于能在纸上画出每一步之后还不让指针串。另一个方法是递归。递归会一层层走到最后一个节点然后在返回过程中修改next指针代码很短但不好理解。我建议先用迭代法练熟再研究递归否则很容易陷入看得懂、写不对的状态。环形检测在OJ里也经常出现核心思想是快慢指针一个每次走一步一个每次走两步如果有环两者一定能在环里相遇。这里有个很值得思考的细节为什么快慢指针相遇之后再用一个指针从头出发和慢指针同步走就能找到环的入口设链表起点到环入口距离为a环入口到相遇点距离为b相遇点到环入口剩余距离为c。慢指针走了ab快指针走了abcb快指针路程是慢指针两倍解出来ac所以从头同步走必然在环入口相遇。2.4 单链表接口的整体设计思路写完一堆方法之后我建议你退一步把这一组接口当成一个面向对象接口定义来看待。所谓接口设计就是要让调用方不关心内部节点指针怎么变只关心插到位置几删掉哪个位置值在不在里面。这也是为什么我在类里把head和len设为私有成员一切对链表的操作都通过公有接口进行。这样的封装还有一个好处以后你想把单链表换成双链表调用方的代码几乎不用改因为公开接口保持一致。好的接口还有一个标志边界行为是确定的。比如insert在非法index上到底是抛异常、返回false还是直接不操作你必须在实现里定下来。我的习惯是抛异常因为静默失败会让调用方莫名其妙。这个设计思路会直接沿用到底下双链表实现。3. 双链表空间换灵活3.1 双链表节点与结构差异双链表和单链表最大的区别就是每个节点多了一个prev指针指向前一个节点。这个多出来的指针让删除节点时可以不用从头遍历去找前驱也让逆向遍历变得容易。代价是每个节点多8字节指针开销并且插入删除时要维护的指针从一根变成两根出错概率翻倍。双链表的节点定义templatetypename T struct DListNode { T val; DListNode* prev; DListNode* next; DListNode(const T v) : val(v), prev(nullptr), next(nullptr) {} };我在实现双链表接口时保留了头节点指针head同时增加了尾节点指针tail。tail的存在让尾部插入和尾部删除都能在O(1)内完成这是双链表最常用的优势之一。注意维护tail意味着每个接口在改变链表结构时都要检查边界节点是否变化这块最容易漏。3.2 双链表的插入删除细节双链表的插入依然有三种边界情况头插、尾插、中间插入。头插时新节点插入到head之前需要设置node-next head如果head不为空还要设置head-prev node然后更新head为node。如果链表本来是空表tail也要指向node。尾插逻辑对称如果tail不为空让tail-next node同时node-prev tail再更新tail为node如果空表头尾都指向该节点。中间插入的核心是找到插入位置当前的节点cur然后建立四根指针关系node-next curnode-prev cur-prevcur-prev-next nodecur-prev node。这里的关键是做第四步时不能丢失指向cur的路径所以顺序不能乱。双链表删除相对简单因为可以直接定位到目标节点cur然后cur-prev-next cur-nextcur-next-prev cur-prev再delete cur。但边界条件仍然是处理头尾cur是头时head cur-nextcur是尾时tail cur-prev。在实际工程里类似的操作逻辑也被用于Linux内核的双链表实现、内存管理里的空闲块链表以及各种LRU缓存。LRU缓存用双向链表配合哈希表删除任意key时可以在O(1)内把节点摘下来这一步全靠prev指针。这是双链表空间换灵活最典型的体现。3.3 单链表与双链表的对比选型单链表和双链表的选择从来不是哪个更好而是哪个更适合当前问题。简单对比对比项单链表双链表节点额外开销1个next指针2个指针删除时找前驱需要从head遍历有prev可直接定位逆向遍历不支持/需要先反转天然支持实现复杂度低中高边界多典型应用哈希表链地址法、邻接表LRU缓存、编辑器undo链我自己的经验是刷OJ时单链表占绝大多数因为题目想考察的是边界处理和指针操作工程里真正设计存储结构时双链表更常见比如底层LRU实现一上来就考虑双向结构。从学习角度先把单链表每个接口做到闭着眼能写再进入双链表这个顺序不能反过来。4. OJ挑战链表题的套路拆解4.1 反转链表迭代、递归、头插法在OJ平台上最常出现的链表题就是反转链表。以LeetCode 206为例输入5-4-3-2-1要求输出1-2-3-4-5。许多新手上来就用三指针迭代写出来才发现中间忘保存next。我提供一个能记牢的说法每次循环里先把cur-next存到tmp再让cur-next反指prev然后prev移到curcur移到tmp。一句话总结就是先保存再断链最后整体往右挪。递归版本逻辑完全不同它需要先递归到链尾再逐层把当前节点的后一节点的next指向当前节点。递归终止条件是空节点或者只剩一个节点。递归的代码短但递归深度等于链表长度遇到超长链表时可能会爆栈这也是OJ题里常被忽略的坑。头插法其实不算第三种思想而是一种实现技巧遍历原链表每拿到一个节点就把它用头插入的方式插到新链表头部。这种方法理解起来最直观尤其适合刚刚手写完单链表的人因为头插你已经实现了只需要在遍历过程中复用即可。4.2 环形链表问题快慢指针环形链表的第一问是判断有没有环对应LeetCode 141。最直观的想法是用哈希表记录访问过的节点但空间复杂度O(n)面试官会继续追问如何做到O(1)答案就是快慢指针。慢指针每次走一步快指针每次走两步如果链表无环快指针会先走到null如果有环快慢会在环内某点相遇。第二问是找到环的入口对应LeetCode 142。核心结论前面已经推导过相遇后让一个指针从链表头开始和慢指针同步每次走一步二者相遇的地方就是环入口。我第一次看到这个结论时也觉得很神奇但你亲手画图验证几组数据后就会深信不疑。注意快指针不一定非走两步但走两步的数学性质最好能保证慢指针入环后的一圈内快指针就会追上它如果走三步两者间距每次缩短2反而可能多绕很多圈推导更复杂。真题里一般不考这种变体但理解原理对后续刷图论题也有帮助。4.3 合并有序链表与删除倒数节点把两个有序链表合并成一个有序链表对应LeetCode 21。常见做法是维护一个哑节点dummy尾指针tail初始指向dummy然后谁的头小就先接谁最后把剩余链直接接到tail后面。dummy节点最大的价值在于省去了对第一个节点到底是谁的讨论最后直接返回dummy-next即可。递归版本更短但工程里我更推荐迭代因为不会有递归深度风险。删除链表的倒数第N个节点对应LeetCode 19也是一道高频题。最朴素的思路是先遍历一遍拿到长度再从头走到len-n的位置删掉两次遍历O(n)。进阶做法是双指针让fast先走n步然后slow和fast同时走当fast走到null时slow正好停在待删除节点的前一个位置一次遍历搞定。这类双指针问题本质上是在利用链表非随机访问的特性用间距来模拟下标差。遇到这种题先写朴素版再优化到双指针版面试官会对你很有好感。4.4 重排链表一道综合题重排链表对应LeetCode 143要求把L0 - L1 - ... - Ln-1 - Ln重排成L0 - Ln - L1 - Ln-1 - ...。这是链表题里综合难度比较高的一道本质上是三个基础能力的组合先用快慢指针找到链表中点并把它切成两半再把后半段反转最后把两个链表交错合并。这三个步骤任何一个做错结果都会乱。我建议你在OJ上挑战这道题之前先把找中点和反转后半段分别练熟。找中点的快慢指针里快指针走两步、慢指针走一步当快指针到尾时慢指针的位置就是中点。这里还要留意链表长度为偶数或奇数时的切分位置不然边界会差一个节点。做完这道题你对链表指针的掌控能力基本就到安全线了。后面再遇到排序链表奇偶链表这类题思路都会顺畅很多。4.5 OJ平台上的刷题建议与调试技巧OJ平台上链表题的输入输出往往已经封装好了你的任务只写核心函数但这也带来一个问题看不到链表全貌不好调试。我的经验是把调试代码写回本地用完整链表类构造数据再调你写的那个核心函数。当本地整体跑通后再把核心函数单独复制到OJ里提交能少走很多弯路。还有一个小技巧OJ提交超时不一定代表算法复杂度差也可能是你无意中写了死循环。链表题最经典的大坑就是在反转或删除时丢失了某个next导致遍历永远走不出去。写完之后建议在本地用一个长度100甚至1000的链表跑一下再想一想如果这个函数被调两次会不会把原链表搞坏。这种破坏性思考是调试链表题的最后一道保险。5. 完整源码与调试心得5.1 单链表完整源码这一节把前面聊的单链表接口用一个完整类整合出来方便你直接编译运行。模板节点类型换成int、string都能跑。我在这份代码里选择不带头节点更贴近OJ输入同时通过私有成员len把长度维护起来。#include iostream templatetypename T struct ListNode { T val; ListNode* next; ListNode(const T v) : val(v), next(nullptr) {} }; templatetypename T class SingleList { private: ListNodeT* head; int len; public: SingleList() : head(nullptr), len(0) {} ~SingleList() { ListNodeT* cur head; while (cur) { ListNodeT* next cur-next; delete cur; cur next; } } bool empty() const { return len 0; } int size() const { return len; } void insert(int index, const T v) { if (index 0 || index len) { throw insert index out of range; } ListNodeT* node new ListNodeT(v); if (index 0) { node-next head; head node; } else { ListNodeT* prev head; for (int i 0; i index - 1; i) { prev prev-next; } node-next prev-next; prev-next node; } len; } void remove(int index) { if (index 0 || index len) { throw remove index out of range; } ListNodeT* cur head; if (index 0) { head head-next; delete cur; } else { ListNodeT* prev head; for (int i 0; i index - 1; i) { prev prev-next; } cur prev-next; prev-next cur-next; delete cur; } --len; } int find(const T target) const { ListNodeT* cur head; int pos 0; while (cur) { if (cur-val target) { return pos; } cur cur-next; pos; } return -1; } void reverse() { ListNodeT* prev nullptr; ListNodeT* cur head; while (cur) { ListNodeT* tmp cur-next; cur-next prev; prev cur; cur tmp; } head prev; } void print() const { ListNodeT* cur head; while (cur) { std::cout cur-val; if (cur-next) std::cout - ; cur cur-next; } std::cout std::endl; } };使用起来很简单SingleListint list; list.insert(0, 10); list.insert(1, 20); list.insert(1, 15); list.print(); list.reverse(); list.print(); list.remove(1); list.print(); std::cout list.find(20) std::endl;5.2 双链表完整源码双链表完整实现放在这里重点看insert和remove的边界条件。我在代码里维护了tail因此尾部插入和删除都是O(1)。#include iostream templatetypename T struct DListNode { T val; DListNode* prev; DListNode* next; DListNode(const T v) : val(v), prev(nullptr), next(nullptr) {} }; templatetypename T class DoublyList { private: DListNodeT* head; DListNodeT* tail; int len; public: DoublyList() : head(nullptr), tail(nullptr), len(0) {} ~DoublyList() { DListNodeT* cur head; while (cur) { DListNodeT* next cur-next; delete cur; cur next; } } bool empty() const { return len 0; } int size() const { return len; } void insert(int index, const T v) { if (index 0 || index len) { throw insert index out of range; } DListNodeT* node new DListNodeT(v); if (index 0) { node-next head; if (head) head-prev node; head node; if (!tail) tail node; } else if (index len) { node-prev tail; if (tail) tail-next node; tail node; if (!head) head node; } else { DListNodeT* cur head; for (int i 0; i index; i) { cur cur-next; } node-next cur; node-prev cur-prev; cur-prev-next node; cur-prev node; } len; } void remove(int index) { if (index 0 || index len) { throw remove index out of range; } DListNodeT* cur head; for (int i 0; i index; i) { cur cur-next; } if (cur-prev) { cur-prev-next cur-next; } else { head cur-next; } if (cur-next) { cur-next-prev cur-prev; } else { tail cur-prev; } delete cur; --len; } void print() const { DListNodeT* cur head; while (cur) { std::cout cur-val; if (cur-next) std::cout - ; cur cur-next; } std::cout std::endl; } };对比单链表你会发现双链表的remove实现因为有了index直接定位目标节点比起找前驱的逻辑更自然。这也是为什么许多实际工程组件里双向链表能成为首选结构。5.3 编译运行与测试建议在本地验证时建议不要急着在main里堆一堆调用而是一边写测试一边对照预期输出。一个简单的测试序列可以这样先构造一个空表依次用insert在头部、尾部、中间位置分别插入打印接着remove头部、尾部、中间的位置打印最后调用reverse打印并检查顺序是否逆过来了。这样手动跑完后核心接口的行为心里就有底了。我还有一个固定习惯写一个压力测试循环一万次随机insert和remove每次操作之后用遍历打印检查长度是否一致。这个方法看起来很笨但真的能把边界条件问题逼出来。很多链表实现看起来逻辑正确一旦随机组合执行就会露出长度错误或者空指针崩溃。如果你把insert和remove放在一起随机跑能连续跑通不崩基本就可以放心拿去OJ提交了。5.4 踩过的坑与排查技巧最后集中说说我自己踩过的坑都是那种报错信息不直接、却又非常典型的链表问题。第一坑是忘记更新长度。单链表类里的len如果不跟着增删同步变化后续查找和删除位置判断会全面乱套。每次修改结构的方法都要在设计阶段就把lenlen--写在注释里提醒自己。第二坑是删除前没有保存后继节点。在删除逻辑里如果你在delete cur之后还去访问cur-next或cur-prev整个程序行为就是未定义。稳妥做法是删节点前把需要用到的新连接全部设置好最后再释放内存。这也是我在上面源码里反复强调顺序的原因。第三坑是反转后没更新head。自己手写的反转函数经常会局部把指针关系改对却忘记把head指向新的第一个节点。白板题里可以靠返回值规避但在类接口里head是唯一入口忘了更新就是把整个链表直接丢掉。第四坑是模板类的代码在多个翻译单元中使用时要处理链接问题。C模板类如果头文件和实现分离很容易出现链接错误。最省事的做法是把整个模板实现放在同一个头文件里这也是我上面源码都写成模板定义和实现一份的原因。排查时我常用的方式是打印每个关键步骤前后的链表顺序或者在每个循环里输出cur的值。最有效率的是先用纸笔画出预期指针变化再对照代码逐行看大多数bug都能在十分钟内定位出来。链表这种东西调试工具帮不了太多最终考验的其实是你对引用关系的脑内建模能力。最后再分享一个我个人的习惯每次写完链表代码我会在纸上把指针变动画一遍尤其是删除和反转。这个动作看起来很原始但真的帮我抓住了无数个边界条件的错误。链表这个老朋友值得你花一个下午把每个接口的手感练出来你在OJ里被它虐过的每一道题都会在未来的面试现场变成底气。