0x3f第 29 天。外卖项目的本地环境今天终于配完了紧接着又改期末卷子改了三个小时本以为今晚会废掉结果翻开链表题的时候精神头又回来了。这篇不写什么大道理就是把我从配置环境、批改卷子到重新梳理 0x3f 链表这一整天的过程原原本本记下来包括链表到底该理解到什么程度、C 和 Python 手写链表怎么下笔、逆置和循环链表有哪些坑以及我实际踩中过的各种断链和死循环。适合正在学数据结构、刷算法题、或者准备带实验课的你参考哪怕你现在对链表还停留在知道有 next 指针的阶段这份记录也够你照着画图、写代码、排错了。1. 第29天的流水账外卖环境、改卷子、链表怎么凑到一起的1.1 为什么这个月叫0x3f可能有人看到0x3f就好奇这到底是十六进制的 63还是某个题库的编号其实两个都对。十六进制里 0x3f 等于十进制的 63我给自己定了个 63 天学习计划每天打一次卡所以就把 0x3f 当成这一期的代号用。还有一层原因很多算法题的题解里喜欢用 0x3f3f3f3f 表示无穷大我借用 0x3f 想提醒自己别把知识学成死数字要像链表一样能灵活连接。第 29 天这个数字本身没什么特殊但习惯的力量开始显现。尤其是今天的事情一件接一件外卖环境配置、改卷子、练链表如果放在一个月前我肯定会焦虑到不知道先干哪件。现在反而把它们当成几个独立的节点配置环境是一个节点改卷子是一个节点链表练习又是一个节点。节点之间靠什么连靠上下文靠时间安排也靠一种把大目标拆成小步骤的思维。这跟链表的本质特别像——每个节点只负责存自己的数据和指向下一个节点的指针整个链表才能顺畅地跑起来。1.2 外卖环境配置其实也是把节点串起来很多朋友以为配置外卖项目的本地环境就是下载个依赖、改几行配置实际做起来完全不是这么回事。我今天从早上开始就在跟数据库、缓存、对象存储、消息队列这些组件打交道。这些东西本身是独立的服务但项目要跑起来必须按照固定顺序把它们串起来先启动数据库再启动缓存然后让后端服务去连接它们最后配置网关和前端联调。这个顺序一旦错了问题就特别诡异。比如我先启动了后端服务数据库还没起来后端并不会立刻报错而是会一直尝试重连日志里全是连接超时。等我把数据库启动完后端又不会自动重连成功必须重启服务。这个场景像不像链表里最常见的错误——拿着一个还没初始化的指针去访问数据我当时脑子里就跳出来一个画面如果每个服务是一个节点那环境配置文件就是每个节点里的 next 指针。指针指错了地方整个调用链就断掉指针指对了服务之间的依赖关系才能形成一条完整的链路。所以我一直觉得配置环境和写链表在思维上高度重叠都要求你先理清谁在谁后面再动手。你可以在配置里随便写端口号、写超时时间但如果节点之间的连接关系是乱的后面的代码再漂亮也没用。这也是我把它放在第 29 天记录里的原因——它不是单纯的技术操作而是对串行依赖的直观训练。1.3 改卷子三小时我看到学生和链表指针犯了同一个错下午改期末卷子改了整整三个小时。这不是因为题量大而是因为同样的错误我反复见到。比如很多学生在写程序题时只考虑了正常情况完全不处理空数组、空表的边界再比如有人初始化变量时漏掉了头节点更新导致后面所有结果全部错位。看到这些卷子上的错误我第一反应不是生气而是特别熟悉——这不就是链表中节点没有接上的经典错误吗学生写数组题时心里可能还有下标越界这根弦但一碰到链表的题很多人就慌了。因为链表没有连续的内存地址也没有 index 可用所有的移动都靠 next 指针。一个问题往往不是逻辑上多难而是把指针指丢了、指反了、或者指到了空地址上。改卷子这活儿让我更清楚地意识到链表不是靠背代码学的是靠在纸上画箭头学的。你看学生为什么错因为他们脑子里没有一个节点加箭头的图自然一下笔就是断链。这三个小时虽然累但反而给我后续复习链表提了个醒教别人容易走进的坑自己复习的时候也要刻意避开。所以晚上我再写 0x3f 链表时每一道题都先在草稿纸上画图把指针的变动用箭头标出来再写代码。这个习惯如果早两年养成我能少掉不少头发。2. 链表到底是什么从数组的痛点到节点思维2.1 数组 vs 链表为什么有了数组还要链表数组是一种连坐式的数据结构一整块连续内存下标可以直接算出地址所以随机访问特别快。但也正因为连续插入和删除的时候就非常痛苦。你在数组中间插入一个元素后面的所有元素都要往后挪一格最坏情况下移动 n 个元素时间复杂度 O(n)。链表就不一样它允许每个节点散落在内存的不同位置节点之间通过指针联系。插入和删除只需要改变相邻节点的指针不需要搬动其他节点时间复杂度 O(1)。我用一个生活例子来解释数组就像电影院连坐票大家必须坐成一排来了一个迟到的人想坐在中间所有人得站起来让座。链表就像一帮朋友分散在餐厅不同桌子各自记着下一个朋友坐在哪新朋友来了只需要让前一个人记下你后面是新人再让新人记下我后面是原来那个人其他人完全不用动。各有利弊。链表虽然插入删除快但查找时只能从头开始顺着指针走随机访问是 O(n)数组则能用二分查找等技巧。而且链表每个节点还要额外存储指针内存开销更大。理解了这些靠取舍才算真正理解了链表存在的意义而不是单纯觉得链表高级。2.2 链表的基本形态单链表、双链表、循环链表链表有几个常见变体。最基本的单链表每个节点包含数据和 next 指针next 指向下一个节点最后一个节点的 next 指向 nullptr。双链表每个节点有 prev 和 next 两个指针可以向前向后走但代价是每个节点多一个指针的空间。循环链表则是把最后一个节点的 next 指向头节点形成一个环循环链表还可以再分单循环、双循环实际工程里最常见的是双向循环链表。不同形态的链表有不同的适用场景。比如 LRU 缓存淘汰算法经常用双链表加哈希表任务调度系统里循环链表可以把任务轮转起来嵌入式系统里内核的定时器列表也大量使用链表。我们学的时候不必贪多先把单链表吃透再把双链表加一个 prev 指针最后再处理循环头尾相接的问题。每一步都建立在画图上而不是死记硬背。2.3 C结构体链表基本语法先写出第一个节点C 里定义链表节点最直接的方式就是结构体。常见写法如下#include iostream using namespace std; struct Node { int val; // 数据域 Node* next; // 指针域指向下一个节点 }; int main() { Node* head nullptr; // 空链表头指针为 nullptr head new Node(); // 申请一个新节点 head-val 1; head-next nullptr; // 目前只有一个节点next 置空 Node* second new Node(); second-val 2; second-next nullptr; head-next second; // 让第一个节点指向第二个节点 cout head-val head-next-val endl; // 输出 1 2 delete second; delete head; return 0; }注意这里的new分配的是堆内存程序结束前要用delete释放。新手最容易漏掉释放或者释放之后还去访问原来的指针这会造成内存泄漏和悬垂指针。更稳妥的做法是每次新建节点后第一时间把它的next初始化为nullptr不要默认它是空。这一步看着简单却能避免很多读取访问权限冲突之类的运行时错误。3. 链表的日常操作遍历、插入、删除画图比写代码重要3.1 链表遍历while 循环和三个最容易犯的错遍历链表是最基础的操作很多人觉得不就一个 while 循环吗实际上手就会发现坑不少。标准的遍历写法如下void printList(Node* head) { Node* p head; while (p ! nullptr) { cout p-val ; p p-next; } cout endl; }第一个常见错误是循环条件写成while (p-next ! nullptr)。这样会导致最后一个节点没有访问到因为当 p 指向最后一个节点时p-next是空循环直接结束。第二个错误是在循环体里打印完p-val后忘记让p p-next造成死循环。第三个错误是在循环体内部不仅移动了p还访问了p-next-val虽然看起来只多了一层访问但只要 p 后面已经空了程序当场崩溃。判断空链表时不要太自信。不管是创建、遍历还是删除第一步都应该问自己如果 head 是 nullptr代码会不会炸很多线上 bug 都是因为只照顾了链表至少有 1 个节点的情况忽略了空链表。写代码之前先在纸上画一下空表、单节点表、双节点表这三种情况再开始写能少 debug 半小时。3.2 链表插入头插法、尾插法、中间插入的顺序问题插入操作有三种头插、尾插、中间插入。头插法最简单核心是两行代码Node* newNode new Node(); newNode-val 0; newNode-next head; // 先让新节点指向当前头节点 head newNode; // 再更新头指针注意顺序不能反。如果先把head设置成新节点再让newNode-next head那newNode就指向了自己后面的节点全部丢失。头插法常用于逆置链表、构建链栈等场景确实很方便。尾插法需要先找到最后一个节点然后把新节点接上去Node* newNode new Node(); newNode-val 0; newNode-next nullptr; if (head nullptr) { head newNode; return; } Node* p head; while (p-next ! nullptr) { p p-next; } p-next newNode;这里我用的是p-next ! nullptr而不是p ! nullptr就是为了让循环结束后 p 指向最后一个节点而不是已经跑出链表。头插法和尾插法选哪个完全看需求。如果频繁在头部操作用头插法如果希望保持原顺序就尾插。中间插入的关键是先接后断。假设要在节点prev后面插入newNodenewNode-next prev-next; // 先把新节点指向 prev 的下一个节点 prev-next newNode; // 再让 prev 指向新节点如果先执行prev-next newNode那么prev原来的下一个节点地址就丢了链表从中间断掉。很多初学者第一次写中间插入都会犯这个错而我自己的经验是永远先把新来的接到后任上再修改前任的指针。这个顺序在双向链表、树、图的各种操作里也通用。3.3 链表删除释放内存不要急先把路搭好删除节点比插入略难因为要同时维护前驱节点和当前节点。如果是单链表删除节点必须知道它的前驱。下面是删除值为特定元素的通用代码void deleteNode(Node* head, int target) { Node* prev nullptr; Node* cur head; while (cur ! nullptr cur-val ! target) { prev cur; cur cur-next; } if (cur nullptr) return; // 没找到 if (prev nullptr) { // 删除的是头节点 head head-next; } else { prev-next cur-next; } delete cur; // 释放内存 }这里有两个容易踩的坑。第一个删除头节点时忘了把head更新成head-next结果操作完头指针还指向已经删除的节点。第二个delete cur之后如果后面又写了prev-next cur-next那等于访问已释放内存必须先改指针再释放。删除的本质是先把前驱的箭头越过要删除的节点连到下下个节点然后再回收这个节点本身占用的内存。顺序反过来轻则断链重则野指针。我把这段话写在这里是因为今天改卷子时真看到学生把步骤写成delete cur; prev-next cur-next;这个错误太典型了。4. 逆置链表与循环链表面试和实验里最常考的变体4.1 单链表逆序三指针迭代法的推演逆置链表是链表的经典题也是很多人第一次接触用纸笔推演算法的题目。所谓逆置就是把 1-2-3-4 变成 4-3-2-1。迭代法用三个指针prev指向前一个节点cur指向当前节点next用来暂存当前节点的下一个节点。代码如下Node* reverseList(Node* head) { Node* prev nullptr; Node* cur head; Node* next nullptr; while (cur ! nullptr) { next cur-next; // 先保存下一个节点 cur-next prev; // 把当前节点指向前一个节点 prev cur; // 前一个节点前进 cur next; // 当前节点前进 } return prev; // 最后 prev 就是新链表的头 }推演的时候要特别注意next cur-next这一步必须在cur-next prev之前执行。因为一旦修改了cur-next原来后面的节点就找不到了。这个先保存再修改的思路和插入操作里的先接后断如出一辙。最后返回的是prev不是cur。当循环结束时cur已经变成nullptrprev才指向原链表的最后一个节点也就是新链表的头节点。很多同学写完后习惯性返回head结果输出的还是原链表顺序。4.2 递归反转代码短但别在面试时翻车除了迭代还可以用递归来逆置链表。递归代码非常短Node* reverseListRecursive(Node* head) { if (head nullptr || head-next nullptr) { return head; } Node* newHead reverseListRecursive(head-next); head-next-next head; head-next nullptr; return newHead; }理解这段代码的窍门在于递归到最深处时函数返回的是原链表的尾节点这个尾节点最终会成为新链表头。递归回调时每一层只做一件事让当前节点后面的那个节点反过来指向当前节点。比如head 1head-next 2递归返回后执行head-next-next head也就是让 2 指向 1同时把 1 的 next 置空。递归虽然优雅但要注意栈深度。如果链表有十万个节点递归可能爆栈。面试时除非你很清楚递归深度可控否则我更推荐迭代法。另外递归代码写起来容易调试却很难一不留神就出现环。我自己的做法是两种都写一遍然后用一个单节点、两个节点的链表做测试确认没有环再收工。4.3 Python 单链表逆序换一种语言思路不变C 写熟了以后换到 Python 其实很简单。Python 里定义节点通常喜欢用 classclass ListNode: def __init__(self, val0, nextNone): self.val val self.next next def reverse_list(head: ListNode) - ListNode: prev None cur head while cur: next_temp cur.next cur.next prev prev cur cur next_temp return prevPython 和 C 的核心逻辑完全一样差异只是语法。但有一个细微的地方Python 对变量赋值的下推逻辑很容易迷惑人。如果你在 while 循环里把prev、cur、next_temp这三行的顺序写反结果同样会断链。所以换语言并没有降低对逻辑的要求反而要求你对每一步箭头更新的本质更清楚。另外Python 刷题时经常用ListNode作为内部类配合类型注解- ListNode可以提高可读性。测试时记得写几百个数据的链表跑一遍别只拿一个三五节点的链表验证。这个经验来自于我实际刷题时的教训小链表能过不代表大链表能过尤其是涉及递归、循环的时候。4.4 循环单链表与约瑟夫环一个让很多人绕进去的栗子循环单链表最大的不同是最后一个节点的next不再指向nullptr而是指回头节点。这个结构的遍历判断条件要从p ! nullptr变成p ! head不然永远走不完。我见过很多人在循环链表里写死循环就是因为套用了单链表的判断方式。约瑟夫环是循环链表的经典应用n 个人围成一圈约定从某个人开始报数报数到 m 的人出列然后从下一个人重新开始直到剩下最后一个人。用循环链表可以很直观地模拟这个过程Node* josephus(int n, int m) { // 先构造循环链表编号从 1 到 n Node* head new Node(); head-val 1; Node* prev head; for (int i 2; i n; i) { Node* cur new Node(); cur-val i; prev-next cur; prev cur; } prev-next head; // 构成循环 Node* cur head; Node* pre prev; while (cur-next ! cur) { for (int i 1; i m; i) { pre cur; cur cur-next; } // cur 是要出列的节点 pre-next cur-next; delete cur; cur pre-next; } return cur; // 最后的幸存者 }这段代码里最需要注意的是删除节点的方式。因为是循环链表大家都有前驱但依然需要用pre记录前驱否则删完节点后无法继续走。而且删除完成后cur要移动到pre-next也就是从下一个节点开始继续报数而不是停留在原地。5. 实操过程记录从 0x3f 题目到手写一遍花了多长时间5.1 我今天实际拿到的 0x3f 链表题长什么样今天复习的题目不算特别难但覆盖面很全。题目大概是这样编写一套单链表的基本操作实验要求实现创建链表、遍历、在指定位置插入、删除指定节点、逆置链表、统计链表长度并且要能处理空链表和单节点链表。这种题目在大学数据结构实验里很常见看起来工程量不大但想一次性跑通并不容易。我给自己定的目标是先不看任何参考代码只在草稿纸上画节点和箭头画清楚后再写 C 代码写完用几个测试用例验证最后再用 Python 写一遍逆置。整个过程花了大约一个半小时比我预想的时间要长。原因在于我在测试边界条件时发现很多代码在链表长度为 1这种极端情况下会出问题。5.2 手写代码的完整流程不是一次写对的我先把一个基本的节点结构写好再写createList函数。创建链表时我喜欢用头插法或者尾插法都行但为了保持题目顺序我选择了尾插法。尾插法的缺点是要每次遍历到最后如果数据量大效率不高但实验场景下节点数通常不多清晰度更重要。真正让我卡住的是删除函数。我刚开始写的时候没有考虑删除头节点的情况结果在测试时head 指向的内容并不是我预期的。后来我在函数参数里加了引用Node* head并且在开头单独判断prev nullptr的情况才算解决。所以写到一半我发现表面上是删节点实际上是在调整头指针的生命周期管理。这个体会不太容易用文字表达但如果你亲手写过一遍你会瞬间明白。花的时间长还有另一个原因我在写完逆置函数后想验证它是否对新链表和旧链表都有意义。于是我打印了反转前后的链表又检查了原链表是否被意外破坏。这个习惯是我后来养成的每次写完链表操作不只看结果对不对还要看原链表是否还完整。链表操作里最常见的隐藏 bug就是改着改着把原链表搞丢了一部分。5.3 我踩过的坑头指针没更新、忘记 delete、循环链表没接尾今天实际踩了三个坑正好对应三个经典问题。第一个坑是头插法时忘了更新head。我规规矩矩写完了newNode-next head然后直接返回结果打印链表时发现新节点根本不在链表中。原因就是这次head变量是函数外面的head我在局部变量里改了它但没传引用也没有把新头返回出去。简单说就是头指针没更新。第二个坑是删除节点后忘记delete。如果只是做题目可能不delete也会得到正确的输出结果因为内存还在只是逻辑上被跳过。但不管做题还是工程内存泄漏都是隐患。尤其是循环链表如果一直new不delete跑一万个人的约瑟夫环内存会一直涨。我这次写完没有立即报错但打印内存快照的时候发现了泄漏于是老老实实补上了每次删除后的delete。第三个坑是构造循环链表时忘了把尾节点的next接回头节点。我一开始把prev-next head放在了循环结束之后但我在循环里已经让prev前移了最后prev恰好是尾节点按理说没问题。问题是如果 n0 或者 n1就需要特殊处理。我为了让实验代码更健壮加了一层判断如果n 0直接返回nullptr如果n 1就让head-next head。否则一运行就把自己绕进去了。6. 常见问题与排查技巧实录改卷子改出来的经验6.1 链表问题速查表我把今天改卷子、写代码时遇到的问题整理成了一张速查表方便你以后照着排查。问题现象可能原因解决办法遍历时漏掉最后一个节点循环条件用的是p-next ! nullptr导致最后一个节点没进循环改成p ! nullptr或者在循环里把最后一个节点单独处理插到链表头后看不到新节点在函数里改了head但没有传引用/没有返回值函数参数用Node* head或者让函数返回新的头指针中间插入后后半段链表丢失先改了prev-next再让newNode-next指向旧的后继永远先接后断先newNode-next prev-next删除节点崩溃删除的是头节点但没有更新head或者访问已释放内存先判断prev是否为空先改指针再delete逆置链表后出现环cur-next被修改后没有暂存next节点逆置循环中先next cur-next循环链表死循环判断条件写成了p ! nullptr改成p ! head并且注意循环链表的头尾连接内存泄漏所有new都有对应的delete了吗用工具或打印检查删除后及时delete这张表不是让你背下来的而是建议你把每个问题都亲手复现一遍。比如故意写错循环条件看输出结果是不是少一个节点故意不更新head看打印结果是不是空。这种故意犯错的实操比看十篇教程都管用。6.2 如何定位断链和死循环链表 bug 最烦人的地方在于出错时程序不一定立刻崩溃而是打印出莫名其妙的结果比如链表里出现了脏数据、或者程序卡死。我现在的排查方法非常简单粗暴在关键节点打印当前指针地址和值。具体来说遍历时可以打印p的地址、p-val、p-next的地址。比如while (p ! nullptr) { cout p p val p-val; cout next p-next endl; p p-next; }这样一眼就能看出链是否断在某一步。如果输出达到某个节点后消失说明这个节点的next出了问题如果输出永远不结束说明链表里出现了环。在代码里加assert(p ! nullptr)也是好办法。尤其是在访问p-next-val之前先断言p-next不是空能从根源上避免空指针访问。我有时候还会在写实验代码时故意在边界处打印一句话比如删除头节点、删除中间节点这样能确认程序走到了哪个分支。改卷子时我也会建议学生在程序里多写这些中间过程的输出至少能让人知道程序为什么没按预期走。6.3 嵌入式链表常见的另类用法内核链表小抄嵌入式开发里链表的使用和课本上有点不一样。常见的内核链表不是把链表节点作为业务结构体的成员而是反过来把链表节点list_head内嵌到业务结构体里。也就是说你定义了一个业务结构体比如记录传感器数据里面有个list_head node然后通过node这个字段把整个结构体串起来。这种设计的好处是通用性极强一套链表操作函数可以服务所有结构体。获取业务结构体地址时使用container_of宏根据链表节点的地址反推结构体起始地址。听起来是不是有点像魔术其实就是用了 C 语言里结构体成员偏移量的计算。这个知识点在嵌入式开发、操作系统内核里特别常见如果你以后要接触驱动开发或 RTOS一定会碰到。我今天复习链表时专门翻了翻内核链表代码发现它里面充满了对节点连接的抽象。它不允许你用head这种业务字段去访问而是用list_entry这类宏统一转换。虽然上手门槛比我这里讲的单链表高一些但底层逻辑仍然是一串箭头。如果你学完单链表后还有精力强烈建议去看一眼嵌入式链表代码示例你会对链表不依赖具体数据这句话有更深的体会。6.4 Java 链表LinkedList 和手写链表的差异如果你用的是 Java可能更熟悉LinkedList这个容器类。它的底层是双向链表而且同时实现了List和Deque接口所以既能当列表用也能当栈和队列用。日常开发直接用它很方便但刷题时面试官更喜欢让你手写一个链表而不是直接调库。手写 Java 链表时需要注意null检查和对象引用。Java 里没有 C 的指针语法但对象引用的行为本质上就是指针的指针。写node.next node.next.next时同样要小心原来的节点被回收。Java 有垃圾回收所以不用担心delete但逻辑上如果丢掉了引用那个节点依然会从链表中消失只是内存由 GC 处理。我在给期末卷子出题时也经常会问学生LinkedList 和 ArrayList 的区别这背后考的就是数组和链表的核心差异随机访问 vs 顺序访问、末尾插入 vs 中间插入、连续内存 vs 零散节点。只要理解了第一性原理换个语言无非就是换个语法糖。你可能会关心的几个补充经验说了这么多我再分享一条今天最真实的感受写链表代码之前先把图画出来。不是那种潦草的草稿而是把每个节点的方框、next箭头、头指针指到哪里都清清楚楚画出来。插入和删除的时候用不同颜色的笔标出先改哪个箭头、再改哪个箭头。这个方法看上去很笨但它能治百病。改卷子时我看到很多学生直接在代码里硬推越推越绕画过图的人至少不会被先接后断这种顺序搞晕。另一个补充经验是给自己限定一个测试用例清单。不要只跑一个正常数据就收工。我今天的清单是这样的空链表、只有一个节点的链表、有两个节点的链表、出现在头部的删除、出现在尾部的删除、逆置一个长链表。每一条都写成一个简单函数跑通了再往下走。这个习惯让我在写实验报告时特别有底气因为不是我的代码能跑而是我知道它在哪些边缘情况下也能跑。最后想说的是今天改卷子三个小时很累但晚上静下心把链表从头画到尾之后整个人反而通透了不少。链表这个东西怕的不是难而是你把它想成一种魔法。其实它就是一组方框和箭头你控制了箭头就控制了整个数据结构。第 29 天过完了明天继续 0x3f 的第 30 天链表还没完但我知道该往哪里使劲了。