链表这东西我在之前的练习记里提过一嘴今天专门拎出来写一篇。原因很简单链表在C算法题里的出场率实在太高了而且它和数组、vector那种“一段连续内存”的直觉完全不同很多新手写起来特别容易栽跟头。我也是从一个个段错误、空指针崩溃里爬出来的所以这篇就把我练习链表时反复折腾过的那些点一次性说清楚——怎么建节点、怎么遍历、怎么在指定位置插入、怎么反转、怎么找中间节点、怎么判环、怎么合并有序链表最后再来点调试技巧和常见坑。这些内容看起来基础但恰恰是后面刷二叉树、图、复杂模拟题的底座值得认真过一遍。这一篇针对的是已经有C基本语法基础至少知道结构体、指针、引用但链表还没形成肌肉记忆的读者。如果你完全没碰过指针建议先补一下指针和内存的基础否则看下面的代码可能会有点吃力。我会尽量在关键地方解释明白但指针的基本概念我不再展开。好直接进入正题。1. 链表的两种C实现方式结构体裸指针 vs 智能指针先说链表节点的定义。C里最常见的两种写法一种是传统的裸指针结构体一种是C11之后用智能指针。绝大多数算法训练和面试场景用的都是裸指针结构体所以这篇也主要围绕这种写法展开。struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} };构造函数这里我建议一定要写。不写的话每次新建节点都得手动赋值node-next nullptr一旦忘了那个指针就是野指针后面遍历的时候随机崩溃排查起来非常折磨。用构造函数一次性把next初始化为nullptr能省掉一大半低级错误。另一种写法是用std::shared_ptr或者std::unique_ptr#include memory struct ListNode { int val; std::shared_ptrListNode next; ListNode(int x) : val(x), next(nullptr) {} };智能指针的好处是内存自动管理不用手动delete特别适合工程代码。但算法训练里我不推荐用原因有三点第一写法啰嗦每次操作都要.get()或者std::move精力被分散第二shared_ptr循环引用会导致内存泄漏链表成环时next互相引用引用计数永远不为0这反而引入新问题第三面试手写代码时面试官通常默认看裸指针写法你上来用智能指针反而可能因为一些边界行为被追问到尴尬。所以这篇的所有代码都用裸指针结构体内存释放的部分我会在最后一节单独说明。另外说一句算法题中链表节点通常不带头结点就是第一个节点就存储有效数据。有的教材喜欢搞一个不存数据的头结点来统一插入删除逻辑这个后面我会单独聊它和“虚拟头结点”技巧的区别。2. 单链表核心操作的C实现从创建到指定位置插入2.1 创建链表头插法和尾插法的差异创建链表有两种基本策略头插法和尾插法。头插法是把新节点插到链表头部最后得到的链表顺序和输入顺序相反尾插法是把新节点接到链表尾部保持输入顺序。尾插法练手时最常用因为它能帮你把“找尾节点”“连接指针”这些基本动作练熟ListNode* createListTailInsert(const std::vectorint nums) { ListNode* dummy new ListNode(0); // 临时头结点后面细说 ListNode* cur dummy; for (int num : nums) { cur-next new ListNode(num); cur cur-next; } return dummy-next; }这里我用了dummy哑结点/哨兵结点它是算法里极其常见的小技巧用一个不参与逻辑的节点统一下一步的插入、删除逻辑。没有它的话尾插法每插一个节点都得判断“链表是不是空的头指针要不要更新”代码会多出不少分支。2.2 遍历链表与统计长度遍历是所有链表操作的基础原理很简单从头指针开始每次访问当前节点的数据然后让指针指向next直到指针为nullptr。int getListLength(ListNode* head) { int len 0; ListNode* cur head; while (cur ! nullptr) { len; cur cur-next; } return len; }这个代码谁都会写但有一个高频bug我见过无数次循环里写成了while (cur-next ! nullptr)。这两者的区别是什么cur ! nullptr允许我们访问最后一个节点后再退出而cur-next ! nullptr会在最后一个节点处停下统计出来的长度少1。很多人在“遍历”和“找尾节点”这两个场景里混用这两种判断条件结果逻辑一团乱。我的经验是需要访问每个节点的数据就用cur ! nullptr只是要找到最后一个节点才用cur-next ! nullptr。2.3 在指定位置插入节点理解前驱节点在指定位置插入节点是链表操作的经典问题它和数组最大的不同就在这里。数组中插入元素得把后面的元素全部往后挪时间复杂度O(n)但物理上元素都在原地链表中插入元素只需要把前一个节点的next指向新节点新节点的next指向原来的下一个节点时间复杂度O(1)——前提是你已经找到了前驱节点。但找前驱节点本身又是O(n)的所以链表插入的整体复杂度还是O(n)。这一点初学者容易混淆以为链表插入是O(1)面试被问到时含含糊糊。准确的说法是插入动作本身是O(1)找到插入位置是O(n)整体是O(n)。下面是在第pos个位置插入节点pos从0开始计数即头节点是第0个的实现ListNode* insertNode(ListNode* head, int pos, int val) { ListNode* newNode new ListNode(val); // 特殊情况插到头部 if (pos 0) { newNode-next head; return newNode; } ListNode* prev head; // 找到第 pos-1 个节点也就是新节点的前驱 for (int i 0; i pos - 1; i) { if (prev nullptr) { // 位置非法链表没那么长 delete newNode; return head; } prev prev-next; } if (prev nullptr) { delete newNode; return head; } newNode-next prev-next; prev-next newNode; return head; }有几个细节值得提插入头部和插入中间要分开处理因为头部插入需要更新头指针本身。这正是不带头结点的链表的麻烦之处。如果你在前面用dummy建链表那么统一处理逻辑会更优雅但这里为了展示“原地操作”的细节我故意保留了分支。循环里for (int i 0; i pos - 1; i)这一步是在走pos-1步跑到第pos-1个节点。写的时候脑子里要清楚头节点是第0个节点它的前驱是空要插到第pos个位置前驱是第pos-1个节点。位置和步数之间差1这是链表题里最容易摔跤的地方。如果位置越界记得delete newNode。很多人写着写着就内存泄漏了练习时无所谓但养成好习惯后面受益。上面这个写法每次插入头部都要单列逻辑代码不优雅。所以实际刷题时我更推荐用一个在所有场景下统一处理的套路——虚拟头结点。2.4 虚拟头结点让插入删除逻辑统一虚拟头结点dummy node和带头结点的链表不是一回事。虚拟头结点是临时的用完就丢带头结点的链表是长久的结构设计。虚拟头结点的核心价值在于它让你不需要特殊处理“操作发生在真实头节点”的情况。ListNode* insertNodeUnified(ListNode* head, int pos, int val) { ListNode* dummy new ListNode(0); dummy-next head; ListNode* prev dummy; for (int i 0; i pos; i) { if (prev-next nullptr) { // 位置越界 delete dummy; return head; } prev prev-next; } ListNode* newNode new ListNode(val); newNode-next prev-next; prev-next newNode; ListNode* newHead dummy-next; delete dummy; return newHead; }注意这里的循环条件变成了i pos。为什么因为prev的初始值是dummy它相当于“第-1个节点”前驱是它自己要插到第pos个位置preve要从dummy走pos步走到第pos-1个节点。这个技巧我第一次遇到时也愣了一下但想通了之后就会觉得特别顺。虚拟头结点在链表题里出场率极高比如删除倒数第N个节点、合并两个链表、反转链表的一部分都能靠它省掉大量边界判断。后面例题里我会反复用到。3. 链表反转迭代法与递归法链表反转是必练题几乎可以说没有之一。它的思路本身不难但第一次写的人很容易被“指针断链”搞晕。3.1 迭代法反转反转的核心思想遍历链表把每个节点的next指向前一个节点。但这会导致原链表断裂所以必须在改变next之前先保存下一个节点。ListNode* reverseListIterative(ListNode* head) { ListNode* prev nullptr; ListNode* cur head; while (cur ! nullptr) { ListNode* nextTemp cur-next; // 先保存下一个节点 cur-next prev; // 反转当前节点的指针 prev cur; // prev 前移 cur nextTemp; // cur 前移 } return prev; // 结束时 prev 指向原链表的最后一个节点也就是新链表的头 }这个代码第一次看会觉得绕但多画几张图就好了。我建议初学的时候拿三个节点手动模拟一遍把每一步的prev、cur、nextTemp指到哪儿画出来比盯着代码看十遍都管用。这里有个细节反转后的头节点是prev不是cur。循环结束时cur是nullptrprev才是原链表的尾巴。很多人漏了这点返回了cur然后调试半天发现返回了个空指针。3.2 递归法反转递归法的写法更简洁但理解门槛高一些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这一步假设head-next后面的子链表已经反转过那head-next现在是子链表的“尾节点”让这个尾节点指回head就等于把head接到了子链表的尾部。递归版虽然代码短但初次接触时强烈建议配合栈的调用过程去理解否则面试时手写容易卡壳。我个人在实战中优先用迭代法因为递归深了可能爆栈而且迭代法空间复杂度是O(1)递归是O(n)。3.3 反转前N个节点和一个区间链表题里还有一种变形不是反转整个链表而是反转前N个或者反转区间[m, n]。这个如果你只背反转整个链表的模板很容易懵。反转前N个节点关键区别在于原来反转完整链表时我们最后让head-next nullptr但反转前N个head也就是反转后的尾节点要接上第N1个节点。所以需要额外记录一个successor节点ListNode* successor nullptr; ListNode* reverseN(ListNode* head, int n) { if (n 1) { successor head-next; // 记录第 n1 个节点 return head; } ListNode* newHead reverseN(head-next, n - 1); head-next-next head; head-next successor; // 指向后面的节点而不是 nullptr return newHead; }反转区间[m, n]就更进一步如果m 1就是上面的reverseN如果m 1就递归往前推进直到头节点变成区间起点ListNode* reverseBetween(ListNode* head, int m, int n) { if (m 1) { return reverseN(head, n); } head-next reverseBetween(head-next, m - 1, n - 1); return head; }这个写法是我见过的最优雅的递归区间反转。理解它的关键还是那句“前驱节点的next要指向翻转后的头”。如果迭代做区间反转思路就变成先走到第m-1个节点然后从m到n逐个将节点“头插”到m-1后面。两种方法都可以但我个人觉得递归在这种题里更不容易把指针绕晕。4. 经典链表算法题快慢指针、合并与排序4.1 快慢指针找中间节点与判断环形链表快慢指针是链表题的黄金技巧没有之一。它的原理很朴素一个指针每次走一步另一个指针每次走两步。当快指针到达链表末尾时慢指针恰好走到中间。ListNode* findMiddleNode(ListNode* head) { if (head nullptr) return nullptr; ListNode* slow head; ListNode* fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; } return slow; }这个返回的是“右中位数”——如果链表有偶数个节点它返回的是第n/21个节点。如果你想要左中位数可以调整初始值或循环条件具体看题目要求。为什么用这个找中间节点重要因为它能把链表从中间断开这样很多“递归合并”“判断回文”的题目就迎刃而解了。比如回文链表判断的经典做法就是先用快慢指针找到中间节点反转后半部分然后逐个比较。判断环形链表同样用快慢指针bool hasCycle(ListNode* head) { ListNode* slow head; ListNode* fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; if (slow fast) { return true; } } return false; }为什么快慢指针在环形链表里一定会相遇很简单一旦两个指针都进入环快指针每次比慢指针多走一步相当于在环里每次“追近”一个节点的距离。环的长度是有限的所以追赶必然成功。这和操场上跑得快的人迟早追上跑得慢的人是一个道理。这里还有一个经常被追问的进阶版如果链表有环如何找到入环点解法也很经典当快慢指针相遇后让慢指针回到头节点两个指针同时每次走一步再次相遇的位置就是入环点。这个结论的推导涉及一点数学但很优美建议自己去推一遍。4.2 合并两个有序链表合并两个有序链表是递归思想在链表里最经典的体现之一。ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (l1 nullptr) return l2; if (l2 nullptr) return l1; if (l1-val l2-val) { l1-next mergeTwoLists(l1-next, l2); return l1; } else { l2-next mergeTwoLists(l1, l2-next); return l2; } }这个递归的优雅之处在于它根本不用考虑“当前谁是谁的前驱”只需要确定“小的那个节点应该接上后面合并好的链表”。每个递归层只返回当前较小的节点作为新链表的头。如果你想用迭代做那就得引入虚拟头结点ListNode* mergeTwoListsIterative(ListNode* l1, ListNode* l2) { ListNode* dummy new ListNode(0); ListNode* cur dummy; while (l1 ! nullptr l2 ! nullptr) { if (l1-val l2-val) { cur-next l1; l1 l1-next; } else { cur-next l2; l2 l2-next; } cur cur-next; } cur-next (l1 ! nullptr) ? l1 : l2; return dummy-next; }迭代版的cur-next (l1 ! nullptr) ? l1 : l2;这行是收尾工作把剩余没比完的链表直接接上。这个操作很多人会忘记导致合并后的链表后半段凭空消失。写完后建议自己检查一下两个链表长度不相等时长的部分有没有被漏掉。4.3 链表的归并排序O(n log n)时间、O(1)空间链表的排序首选归并排序。原因很直接链表的物理结构决定了它不适合快速排序里的“随机访问”和“从后往前扫描”而归并排序只依赖“从前向后”的遍历天然适配链表。而且在空间上数组归并排序需要额外O(n)的辅助数组链表归并排序只需要O(1)的额外空间递归栈除外。核心步骤就三步找中点、递归排序两半、合并两个有序链表。ListNode* sortList(ListNode* head) { if (head nullptr || head-next nullptr) { return head; } // 1. 找中点 ListNode* slow head; ListNode* fast head; ListNode* prev nullptr; while (fast ! nullptr fast-next ! nullptr) { prev slow; slow slow-next; fast fast-next-next; } prev-next nullptr; // 断开为两段 // 2. 递归排序两半 ListNode* left sortList(head); ListNode* right sortList(slow); // 3. 合并 return mergeTwoLists(left, right); }注意这里找中点和前面略有不同需要额外用一个prev记录中点的前一个节点然后把它和后面断开。如果忘了断开递归时链表还是完整的一条结果就是死循环——递归永远切不到单节点。这个排序是面试链表时的常客建议多写几遍直到能一次性通过。链表的mergeTwoLists我们可以直接复用上一节的代码。4.4 环形链表II找到入环点之前提到过入环点的问题这里直接给出完整推导和代码。ListNode* detectCycle(ListNode* head) { ListNode* slow head; ListNode* fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; if (slow fast) { // 相遇了说明有环 slow head; while (slow ! fast) { slow slow-next; fast fast-next; } return slow; } } return nullptr; }为什么第二次相遇时就是入环点假设从链表头到入环点的距离是a入环点顺时针到第一次相遇点的距离是b环的剩余长度是c。第一次相遇时快指针走了a n(bc) b慢指针走了a b。因为快指针速度是慢指针的两倍所以2(ab) a n(bc) b化简得a (n-1)(bc) c。也就是说从头节点到入环点的距离等于从相遇点继续走c再加上若干圈环。所以让一个指针从头开始一个从相遇点开始每次都走一步必然在入环点相遇。这个推导建议自己推一遍面试时如果直接背结论被追问“为什么”容易卡壳。5. 链表删除操作虚拟头结点的经典场景5.1 删除指定节点ListNode* deleteNode(ListNode* head, int val) { ListNode* dummy new ListNode(0); dummy-next head; ListNode* cur dummy; while (cur-next ! nullptr) { if (cur-next-val val) { ListNode* toDelete cur-next; cur-next cur-next-next; delete toDelete; return dummy-next; // 只删第一个匹配的节点 } cur cur-next; } return dummy-next; }这里用cur-next来判断是为了在删除时能方便地让前驱的next跨过被删除节点。如果直接用cur判断删除时还得额外保存前驱代码反而更长。删除后记得deleteC不用手动释放内存的语言没这个烦恼但C里忘了就是泄漏。5.2 删除倒数第N个节点这个题也是经典中的经典。思路用快慢指针快指针先走n步然后快慢指针一起走当快指针到末尾时慢指针正好在倒数第n个节点的前一个节点。ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy new ListNode(0); dummy-next head; ListNode* fast dummy; ListNode* slow dummy; // 快指针先走 n1 步 while (n 0 fast ! nullptr) { fast fast-next; --n; } // 快慢指针一起走 while (fast ! nullptr) { fast fast-next; slow slow-next; } // 此时 slow 指向倒数第 n1 个节点 ListNode* toDelete slow-next; slow-next slow-next-next; delete toDelete; return dummy-next; }为什么要让快指针先走n1步而不是n步因为删除倒数第n个节点需要找到它的前驱也就是倒数第n1个节点。n1这个偏移常常让第一次写的人懵不妨记住慢指针最后停的位置就是你确切要操作的节点的前一个。先走n1步等快指针到末尾时慢指针自然就停在了倒数第n1个节点上。6. 两个进阶练习链表的相交与重排6.1 相交链表找出两个链表的交点这个题的优雅解法是双指针交替走两个指针分别从两个链表头出发每次走一步走到末尾后跳到另一个链表的头部继续走。如果两个链表相交两个指针会在交点相遇如果不相交它们会同时走到nullptr。ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) { ListNode* pA headA; ListNode* pB headB; while (pA ! pB) { pA (pA nullptr) ? headB : pA-next; pB (pB nullptr) ? headA : pB-next; } return pA; // 如果没交点两个指针最终都是 nullptr }这个解法的时间复杂度是O(mn)空间复杂度O(1)不用额外记录走过的节点。原理也很直观两个指针走过的总路程相同分别是mn和nm如果存在交点它们必然在走过的最后一步之前相遇。6.2 重排链表快慢指针反转合并这个题综合了前面好几个技巧特别适合用来检验自己链表的基本功是否扎实给定链表1-2-3-4-5重排成1-5-2-4-3。思路是三步走先用快慢指针找到中间节点把链表拆成前后两段把后半段反转然后把后半段交替插入前半段。void reorderList(ListNode* head) { if (head nullptr || head-next nullptr) return; // 第一步找中间节点 ListNode* slow head; ListNode* fast head; while (fast-next ! nullptr fast-next-next ! nullptr) { slow slow-next; fast fast-next-next; } // 此时 slow 是左半段的尾节点 // 第二步反转后半段 ListNode* secondHead reverseListIterative(slow-next); slow-next nullptr; // 断开 // 第三步交替合并 ListNode* first head; ListNode* second secondHead; while (second ! nullptr) { ListNode* temp1 first-next; ListNode* temp2 second-next; first-next second; second-next temp1; first temp1; second temp2; } }注意这里找中间节点时循环条件是fast-next ! nullptr fast-next-next ! nullptr这会让奇数长度时slow停在正中间偶数长度时停在偏左的位置。这样拆出来的左半段长度不少于右半段交替合并时才不会出现second比first长导致的问题。这个题我第一次写的时候因为拆的时候没把slow-next置为nullptr结果合并时链表出现了环直接死循环。这种“断链”的坑在链表题里太常见了值得时刻警惕。7. 链表题的调试技巧与C内存管理7.1 打印链表写一个辅助函数链表调试最大的痛点是看不见内部状态。数组在IDE里可以直接看元素链表只能靠眼睛逐节点确认。所以我的习惯是第一时间写一个打印函数void printList(ListNode* head) { ListNode* cur head; while (cur ! nullptr) { std::cout cur-val; if (cur-next ! nullptr) { std::cout - ; } cur cur-next; } std::cout std::endl; }每次操作完打印一次配合断点绝大多数链表bug能在五分钟内定位。注意循环条件用cur ! nullptr才能把最后一个节点也打出来。7.2 常见错误盘点见下表错误类型表现根因解决办法野指针访问随机崩溃节点next没初始化就使用构造函数里初始化nextnullptr死循环程序卡死不退出链表成环常见于断开链表时漏掉nextnullptr拆分链表后立刻检查断点空指针解引用segfault未检查headnullptr就访问head-val操作前先判空返回错误的头指针输出少了或多了节点删除/反转时没有更新头指针用dummy或在return处明确返回新头长度边界差1删除错了位置循环步数和下标混淆手动模拟3个节点走一遍内存泄漏长时间运行内存上涨删除节点没delete每次删除节点都手动释放7.3 内存释放问题C里new出来的链表节点不会自动释放。练习时无所谓但工程上严谨的析构应该写一个销毁函数void deleteList(ListNode* head) { while (head ! nullptr) { ListNode* next head-next; delete head; head next; } }如果链表有环这个函数会死循环。所以释放前要先判环。这也是为什么算法题里我建议先用裸指针把逻辑练明白什么时候该释放、什么时候不该释放比如节点还挂在别人的链表里心里要有数。换成智能指针虽然能自动管理但循环链表这种场景反而更容易踩坑。7.4 实例调试一次完整的段错误排查给你看一个我真实的踩坑过程也许比背代码更能培养感觉。有一次我在写“删除指定位置的节点”时写完自信满满去跑测试结果一运行就段错误。我排查的步骤是先打印一下链表确认链表本身没问题然后二分定位在删除函数的入口、循环体内部各打一个日志很快就发现循环里第一次访问cur-next-next时cur-next已经是nullptr了等于在访问nullptr-next自然崩溃。根因是循环的终止条件写错了——我在删除节点后没有及时更新循环判断导致越界访问。这种问题看代码很难看出来但打印日志的方式可以秒定位。所以别觉得自己“应该能看出来”就不打印日志是链表调试最好的朋友。8. 从练习到工程链表的性能边界与场景选择最后聊聊工程视角下的链表。虽然算法题里链表很重要但在真实的生产代码里链表的出场率其实没想象中高。原因在于链表的内存访问是跳跃式的CPU缓存命中率远低于连续内存的vector所以即使时间复杂度一样实际性能也可能差出数倍。链表每个节点都要额外存储一个指针内存开销大节点分散在堆上频繁插入删除时内存分配器压力大。所以工程里如果你需要频繁在中间插入、删除且节点数量很大更常见的做法是用std::deque、std::list这本身就是双向链表或者引入“块状链表”“跳表”这些结构来兼顾性能。但这不代表链表白学了。链表的练习真正锻炼的是三件事指针操作的严谨性、边界条件的敏感度、递归和迭代两种思维的无缝切换。这些能力在写操作系统代码、实现数据库存储引擎、设计缓存淘汰策略时都会有直接的回报。也就是说链表题不只是为了考试它是在帮你建立操纵内存的直觉。我自己练链表时有个习惯不管多简单的题拿到以后先画图再写代码最后用三五个边界用例验证空链表、单节点、双节点、头尾操作。这套流程写熟了后面碰到的很多复杂数据结构题目都会轻松不少。如果你现在正处于“链表题看不懂、写不对”的阶段先别急着跳题把这篇里的代码一个个敲下来跑通再试着改条件看输出变化。链表这关过去了后面很多路就顺了。