1. 链表的核心概念与思考框架1.1 从数组到链表指针到底指了个什么打开编辑器新建一个 cpp 文件接着写链表。这是 C 算法练习系列的第二次内容很基础但基础的东西往往最要命——笔试面试都喜欢从链表切入考代码功底很多框架源码、内存池、内核里的数据结构也都长在链表上。刷题之前不把链表的底子打扎实后面写二叉树、图、LRU 缓存时还得回头补课。先想清楚一个问题已经有了数组为什么还需要链表数组在内存里是一段连续空间。你想在中间插入一个元素就要把后面的数据全部往后挪插入是 O(n)删除同理也要搬家。链表做的事情很朴素不要求大家挨着坐每个元素分头记住“下一个人在哪”用 next 指针把分散的内存串起来。这样插入和删除只需要改指针不需要搬动整段数据代价是失去了“按下标直接访问”的能力。链表的最小单元是节点Node在 C 里通常用结构体定义。节点里放数据再加一个指针指向下一个节点struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} };这段代码背后最关键的点是“指针”这个类型。很多新手看见 ListNode* 就头晕其实可以把它理解成一扇门上的门牌号——它自己不是那间屋子它只是告诉你屋子在哪儿。next 指针存的也不是节点本身而是下一个节点的地址。想访问它指向的节点用箭头操作符 -ListNode* p new ListNode(1); // 创建节点 p-next new ListNode(2); // 在它后面接一个新节点p-next 的值是第二个节点的地址但 p-next 本身又是个指针。这种“指针指向存着指针的地方”的嵌套结构是链表里所有复杂操作的核心。1.2 单链表、双链表与循环链表怎么选链表有不少变体算法题里最常见的几种要分清不然题目里出现“双向链表”“循环链表”时容易看懵。单链表每个节点只保存 next 指针只能从前往后走。删除一个节点时必须拿到它的前驱节点才能把链条重新接上所以遍历时要维护一个 pre 指针跟着当前节点走。这是最常考的类型也是这篇文章的主角。双链表每个节点多一个 prev 指针可以双向遍历。C 标准库里的 std::list 就是双向链表。删除节点时不需要找前驱能 O(1) 完成代价是多占一个指针的空间操作时也多了一处需要维护的指针。循环链表是单链表的一种变体尾节点的 next 不指向 nullptr而是指回头节点整个链表首尾相连。约瑟夫环这类问题就是循环链表的典型场景环形链表判环也可以借用它的思路。带头结点和不带头结点的区别也要讲清楚。头结点dummy node / 哨兵节点不存实际业务数据它存在的唯一意义是“让空链表和非空链表的处理逻辑统一”。不带头结点时插入到第一个位置和插入到其他位置代码逻辑完全不同带头结点后所有插入本质上都变成了“在某节点后面插入”省掉了一堆 if 分支。算法题里用 dummy 节点能简化太多代码后面写删除倒数第 N 个节点这类题时感受会特别明显。三种结构的对比整理成一张表方便记忆类型额外指针遍历方向删除复杂度典型应用单链表next单向O(n) 需要前驱算法题、哈希链双链表next prev双向O(1) 拥有前驱LRU 缓存、std::list循环链表视类型而定环形同单/双链表约瑟夫环、任务轮询2. 构建链表头插法、尾插法与在指定位置插入2.1 节点定义结构体的基本语法刷题时手动定义链表节点是家常便饭。LeetCode 风格的节点定义基本是统一的struct ListNode { int val; ListNode* next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode* next) : val(x), next(next) {} };一个节点里同时保存数据 val 和指向下一个节点的指针 next。构造函数里用初始化列表给成员变量赋初值是 C 比较好的习惯——比在函数体里赋值更高效也更安全。有些新手会把 struct 和 class 混着用其实都行但刷题时用 struct 更方便因为默认成员是 public 的访问起来不用写一堆 public:。2.2 头插法顺序会反转的构建方式构建链表最常用的两种方式是头插法和尾插法。头插法每次都把新节点插到链表头部新来的节点会成为新的头节点。ListNode* createByHeadInsert(vectorint nums) { ListNode* head nullptr; for (int num : nums) { ListNode* newNode new ListNode(num); newNode-next head; head newNode; } return head; }为什么每次都更新 head因为新节点插在最前面原来的头节点就变成了第二节点链表头指针必须跟着变。这段代码执行完输入数组 [1, 2, 3] 会得到 3 - 2 - 1因为每次新节点都压到了最前面。头插法的优势是 O(1) 完成插入不必遍历找尾节点。建立完的链表与原序列正好相反这个性质可以用来做反转链表——如果一个节点一个节点地往前插链表顺序自然反过来了。2.3 尾插法保持输入顺序的稳妥方案尾插法维护一个 tail 指针指向当前链表末尾每来一个新节点就挂在 tail 后面ListNode* createByTailInsert(vectorint nums) { ListNode* dummy new ListNode(0); // 哨兵节点 ListNode* tail dummy; for (int num : nums) { ListNode* newNode new ListNode(num); tail-next newNode; tail newNode; } return dummy-next; }这里我特别用了 dummy 哨兵节点目的就是把“第一节点插入”和“后续节点插入”的逻辑统一起来。如果没有 dummy第一次插入时需要先给 head 赋值后面又走到 tail 分支代码里必然多一个 if。用 dummy 后不管链表空不空插入逻辑都一模一样final 返回 dummy-next 就是真正的头节点。尾插法保持了元素的相对顺序构建出的链表和数组顺序一致更符合常规认知。代价是比头插法多维护一个 tail 指针但代码复杂度没有明显增加。2.4 在指定位置插入先把边界条件想清楚这是链表基础操作里最容易错的一步热词里“在指定位置插入建立单链表”问的人特别多。先定义清楚要解决的问题给一个头节点 head在第 pos 个位置0 为起始下标插入新节点 newNode。实现之前先想边界条件pos 0插到头部整个链表的头要换人。pos 等于链表长度插到末尾。pos 非法小于 0 或超过链表长度返回错误或者直接不处理。链表为空时pos 必须为 0 才有意义。我用 dummy 哨兵统一逻辑bool insertAtIndex(ListNode* head, int pos, int val) { if (pos 0) return false; ListNode* dummy new ListNode(0); dummy-next head; ListNode* pre dummy; int step 0; while (pre step pos) { pre pre-next; step; } if (pre nullptr) return false; // pos 超过了链表长度 ListNode* newNode new ListNode(val); newNode-next pre-next; pre-next newNode; head dummy-next; delete dummy; return true; }这里用 ListNode* head 传引用是因为头部可能被替换在函数内部修改 head 后要带回给调用者。如果你写的是 ListNode* head 而不是引用函数内部改 head 只改了副本外层拿到的还是旧头节点这是经典的是个送分题也是送命题的细节。顺序插入的核心思想只有两行newNode-next pre-next; pre-next newNode;顺序绝对不能反。如果先执行 pre-next newNode原本 pre 后面的那段链表就丢了newNode 根本找不到自己的后继。先把新节点的 next 接好再让前驱指向新节点链条才会无缝衔接。我见过不少新手在这一步翻车写反之后链表直接断成两截。这背后其实是对“指针赋值”的直觉节点 A 的 next 是地址节点 B 的地址在别处改动 A-next 不会影响 B 内部的 next。把地址关系图画出来一眼就能看明白。3. 链表基础操作遍历、删除与反转3.1 遍历与查找老三样遍历是链表的万能基本功。核心代码很短void printList(ListNode* head) { ListNode* cur head; while (cur ! nullptr) { cout cur-val - ; cur cur-next; } cout null endl; }这里有个值得抠的细节什么时候用 cur ! nullptr什么时候用 cur-next ! nullptr用 cur 判断时循环体内可以处理当前节点本身适合打印、统计、查找值。用 cur-next 判断时循环体结束的位置是倒数第二个节点适合做“在链表末尾插节点”“找倒数第 N 个节点”这类需要停在特定位置的操作。查找某个值是否存在于链表里基本就是遍历加判断bool findValue(ListNode* head, int target) { ListNode* cur head; while (cur cur-val ! target) cur cur-next; return cur ! nullptr; }返回值用了很关键的技巧cur 为 nullptr 表示没找到cur 不为空说明找到了那个节点。不需要额外变量打标记。3.2 删除节点别让节点失联删除节点的关键是找到前驱。因为单链表没有往回的指针不拿到前驱就没法把断掉的链重新接上。删除值为 target 的第一个节点ListNode* deleteNode(ListNode* head, int target) { ListNode* dummy new ListNode(0); dummy-next head; ListNode* pre dummy; ListNode* cur head; while (cur) { if (cur-val target) { pre-next cur-next; delete cur; break; } pre cur; cur cur-next; } return dummy-next; }删除动作本质上就是让 pre 跳过 cur直线指向 cur 的下一个节点。然后 delete 掉被删除节点的内存这是 C 特有的内存管理要求——用裸指针 new 出来的节点必须手动释放否则内存泄漏。如果不带头结点删除头节点时 head 本身需要更新。用 dummy 之后所有删除都变成了普通情况这也是为什么我一直推荐哨兵节点。注意如果不止删除第一个匹配节点而是删除所有匹配的节点循环逻辑要做点调整。删除当前节点后 pre 不动cur 挪到 pre-next跳过不匹配时 pre 和 cur 一起往后走。细节不同思路相同。3.3 反转链表高频题必须背熟反转链表是链表面试题中的王者几乎人人必刷。LeetCode 206 就是这道经典题用迭代法最好理解ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; ListNode* cur head; while (cur) { ListNode* next cur-next; // 先记住后继不然断开就没地方去了 cur-next prev; // 指针反转 prev cur; // prev 前进 cur next; // cur 前进 } return prev; }用三个指针走完整个链表。每一步做的事都一样先把 cur 的下一个节点存好否则改变 cur-next 的指向后原来后面的节点就“失联”了然后让 cur 掉头指向 prev再整体右移。循环结束时 cur 是 nullptrprev 停在新的链表头直接返回 prev。这个题强烈建议自己画图理一遍两个相邻节点看它们的 next 从 a-b 变成 b-a 后第三个节点是不是还挂在 b 的 next 后面。画完一次就再也不会忘记为什么要先存 next。递归写法也很漂亮但递归理解起来比迭代陡峭ListNode* reverseListRecursive(ListNode* head) { if (head nullptr || head-next nullptr) return head; ListNode* newHead reverseListRecursive(head-next); head-next-next head; head-next nullptr; return newHead; }递归解法的关键点先让后面的链表完成反转此时 head 的 next 指向的节点已经变成了反转链表的尾节点再让这个尾节点的 next 指回 head相当于把当前节点接到新链表尾部。递归基本功不扎实的话先用迭代把递归这个进阶版放着以后吃透。3.4 快慢指针找中间节点、判环快慢指针是链表题里另一大流派。它解决的问题很广泛找链表中间节点、判断链表是否有环、找到环的入口、寻找倒数第 K 个节点。找中间节点的写法ListNode* middleNode(ListNode* head) { ListNode* slow head; ListNode* fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; } return slow; }slow 每次走一步fast 每次走两步。fast 到终点时slow 正好在链表中点。对于偶数长度的链表这个写法返回偏右的那个节点如果想返回偏左节点只要把循环条件调整一下或者用一个小偏移。这种细节在面试题里经常被拿出来抠建议提前想好自己默认返回偏哪边。判断链表是否有环的核心逻辑类似fast 如果走进环里因为每轮快指针比慢指针多走一步二者最终一定会相遇。一旦 fast slow 就说明有环。bool hasCycle(ListNode* head) { ListNode* slow head, * fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) return true; } return false; }这里有个容易忽略的点slow 和 fast 都从 head 出发判断是否相遇要放在指针移动之后而不是进入循环时。否则初始状态 slow fast直接误判成有环。4. 从基础练习到实际应用4.1 常见链表面试题整理链表题有一定的模式常见的题基本都在下面这张清单里题目类型核心考点典型题目构建链表头插法、尾插法、哨兵节点连续输入建表删除节点前驱查找、哨兵点LeetCode 203 移除链表元素反转链表双指针、迭代/递归LeetCode 206 反转链表环形链表快慢指针LeetCode 141 / 142合并有序链表双指针、巧用哨兵LeetCode 21 合并两个有序链表删除倒数第 N 个节点双指针距离控制LeetCode 19两数相加逆序链表模拟加法LeetCode 2链表排序归并排序、递归拆链表LeetCode 148 排序链表很多人刷题时东一道西一道没有章法。我建议按“会构建 → 会增删改查 → 会反转 → 会双指针 → 会合并排序”这个顺序来每个阶段找两三道题练熟不要一上来就碰链表排序。4.2 排序链表归并排序在链表上的实现热词里出现了“归并排序算法”链表中高阶一点的操作就数排序了。LeetCode 148 要求将链表排序要求时间复杂度 O(n log n)、空间复杂度 O(1)。用数组里学的快速排序、堆排序都不太方便因为链表不支持 O(1) 随机访问而归并排序天然适合链表这种“只需要不断找中点再合并”的数据结构。先找链表的中点切成两半递归排序再合并两条有序链表。合并部分的代码和合并两个数组非常像区别只是不申请额外数组穿针引线一样把节点串起来。ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode* dummy new ListNode(0); ListNode* tail dummy; while (l1 l2) { if (l1-val l2-val) { tail-next l1; l1 l1-next; } else { tail-next l2; l2 l2-next; } tail tail-next; } tail-next l1 ? l1 : l2; return dummy-next; }这个写法里有一个可以背下来的细节最后那行 tail-next l1 ? l1 : l2处理了两条链长度不一致的情况避免再写一个 while 循环去搬运剩余节点。因为剩余节点本身已经是排好序的把链头接上就完事。完整排序链表的框架ListNode* sortList(ListNode* head) { if (!head || !head-next) return head; ListNode* mid middleNode(head); // 找中点 ListNode* left sortList(head); // 递归排左半 ListNode* right sortList(mid); // 递归排右半 return mergeTwoLists(left, right); // 合并 }这里找中点时要注意如果中点计算让左右两半分配不均递归会无限循环。推荐用“slow 从头节点出发、fast 从头节点的 next 出发”的组合来切分ListNode* middleNode(ListNode* 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; // 关键一步切断链表 return mid; }这样 slow 停在前半段的最后一个节点把它的 next 置空链表正式一分为二两个半段都变成独立的链表。忘记切断的话递归排序时会死循环。4.3 做题的顺序与刷题思路不少初学者喜欢看完题解直接抄代码第二天全忘了。链表这种数据结构特别适合纸上推演建议每个算法都先自己在草稿纸上画出节点和指针变化再对比代码实现。我练链表时的一个习惯是定义一个几乎不变的 printList 调试函数每完成一步操作就输出一次链表内容。比如做完插入操作后打印一次做完删除后打印一次。虽然写算法题时不要求但你自己调试复现时这东西能救命。链表的段错误不好直接定位能把每一步的结构变化看清楚了问题自然浮现。还有一个小建议刷链表题时尽量用自己的本地环境跑用例而不是全靠在线判题。本地环境配合断点调试能清晰观察到每个指针的值和 next 的变迁理解深度完全不一样。5. 调试与内存安全新手最该补的课5.1 空指针几乎每个新手都翻车链表代码常见的崩溃原因就是空指针访问。典型的场景ListNode* cur head; while (cur-next) { // 如果 cur 已经是 nullptr程序直接崩 cur cur-next; }这种错误在内存里表现为访问了非法地址系统直接抛出段错误Windows 上有时会看到 memory access violation 之类的报错。掌握一个原则使用 cur-next 之前必须先确认 cur 不为空。反过来使用 cur-val 之前也要先确认 cur 不为空。防御式写法是循环条件显式判断两者比如 while (cur cur-next)这样 cur 为 nullptr 时循环直接退出不会执行内部访问。还有一种利用“短路求值”的常见写法if (cur cur-val target)cur 为 nullptr 时不看后面的条件会直接判断为 false。5.2 内存管理new 了就要 deleteC 链表和 C 语言链表写法上很像但多一层内存管理的坑C 用 malloc/freeC 用 new/delete。很多教材只在介绍语法时提了 delete实践时大家却常常忘记。每次 new 一个节点都必须在合适的位置 delete 它。链表销毁的典型写法void destroyList(ListNode* head) { ListNode* cur head; while (cur) { ListNode* next cur-next; delete cur; cur next; } }注意又要先保存 next 再 delete。delete 释放当前节点的内存之后再访问 cur-next 来取后继已经属于“读已释放内存”属于未定义行为所以我先把 next 存下来。这个模式也是链表编程中反复出现的“保存后手”思想。如果你不想手动管理内存可以用 std::shared_ptr 或 std::unique_ptr 包一下节点这样节点析构时自动释放。但算法竞赛和面试场景里大家几乎不用智能指针写链表因为标准库的形式更复杂而且写裸指针更能体现对内存布局的理解。我的建议练习时用裸指针生产代码里倾向智能指针各有各的适应场景。5.3 开发环境配置与调试技巧热词里出现了“vscode配置c/c环境”确实VS Code 是目前写 C 算法练习最轻量的编辑器比打开一个庞大的 IDE 快得多。但新手的痛点在于代码能编译却没法调式或者 task 配置出了问题连编译都过不了。简单梳理一下 VS Code 下的流程。你需要安装 C/C 扩展插件然后准备 tasks.json 负责编译{ version: 2.0.0, tasks: [{ label: build, type: shell, command: g, args: [-g, ${file}, -o, ${fileDirname}/${fileBasenameNoExtension}.exe] }] }关键是 -g 参数它让编译器生成调试信息否则断点无法命中。launch.json 负责调用调试器{ version: 0.2.0, configurations: [{ name: debug, type: cppdbg, request: launch, program: ${fileDirname}/${fileBasenameNoExtension}.exe, stopAtEntry: false, externalConsole: true }] }配置好之后可以在链表的入口处打一个断点逐行观察 head、cur、cur-next 的变化。我给新手调试链表的建议是把鼠标悬停在指针变量上点开箭头看它指向的节点再展开 next 链能看到完整的链表结构。这一招比打印一百遍 log 都管用。Windows 上如果 g 命令不可用一般是编译器环境变量没配好。安装 MinGW 后把 bin 目录加到 PATH 里就能解决。某些机器装了 Visual Studio 之后自带 MSVC 编译器也可以配置 cl 命令的编译任务只是工具链略有不同使用上并不复杂。6. 那些我踩过的链表坑与练习心得6.1 画图比看代码靠谱听我说一句链表题目不要一上来就在编辑器里闷头写。先拿笔画一条长链表然后模拟每一步操作把要修改的指针圈出来先把要改哪几个地方标清楚再动键盘。比如反转链表那题画 1 - 2 - 3标出 cur 和 prev 的初始位置然后走一步看一步。一整个画完你会发现自己对指针操作的理解比刷十道题还深。我教过的很多新人都是从画图开始慢慢建立起“指针是地址、指向关系是链条”的空间感后面二叉树和图就都好学了。6.2 用最小的用例验证每次写完一个函数先别急着跑大用例。空链表、单节点链表、两个节点的链表这三个测试用例几乎能覆盖掉链表操作里百分之八十的边界问题。比如删除节点时删头节点和删中间节点逻辑完全不同反转时空指针和单节点也要单独处理。养成习惯每次写完都先跑这三个用例段错误概率会大幅降低。除了手动构造测试用例写代码时也可以顺手加 two 三个 assert。C 的 assert 宏在 debug 模式下非常好用比如删除后可以 assert(pre-next cur-next)快速发现指针逻辑错的节点。虽然刷题时不要求但它能救你一命。6.3 链表的边界条件清单给你一份可以抄的边界条件速查表做链表题前对着看一遍链表为空head nullptr 时函数是否能正确返回只有一个节点操作后 head 是否还是原来的节点操作头部是否需要更新 head用不用 dummy 简化操作尾部遍历时 cur 和 cur-next 的判定是否搞混反转操作新链表尾部是否有人记得置空删除操作还记得先取 next 再 delete 吗快慢指针fast 为 null 时循环退出条件正确吗6.4 后续还能练些什么链表这关过了之后二叉树、图这类“指针结构”的题目会有天然的上手优势因为核心都是节点和指向关系的变化。我自己练完链表再去碰二叉树的遍历和翻转明显感觉到了知识的迁移。另外千万别小看链表在生产环境里的价值。操作系统内核里的任务队列、游戏引擎里的对象池、内存管理里的空闲块链表全都是链表思想的延伸。面试官考链表很多本质上是在考你有没有理解“数据在内存中不连续时如何组织访问逻辑”这件事。我个人的体会是链表真正难的不是增删改查那几个固定套路而是能不能在没有任何提示的情况下自己把边界情况和指针变化想清楚。画图、断点调试、用最小用例反复验证这三板斧能帮你杀掉大部分潜在 bug。写熟了之后再做几道衍生题感觉会特别顺。