链表核心操作与面试高频题详解：从单链表到双链表和循环链表

1. 为什么要学链表数组的局限和链表的本质我第一次觉得链表这东西必须讲透是因为带过一个刚转行学编程的学弟。他写了半年数组觉得“数据结构”四个字就是考试用的直到某天他接到一个需求在一个不定长列表里频繁插入数据每次往中间插一条数组就得把后面所有元素整体后移一千万条数据插一次就要卡几秒。他跑来问我有没有一种结构插得特别快又不提前定长度我说有链表。链表数据结构里最基础也最容易被初学者绕晕的一章。它和数组最大的区别说人话就是数组是一排连续的座位坐满了就得整体搬家链表是一串手拉手的积木块每个块只知道下一个块在哪想加一块随便找个地方接上就行。正因为这种“不连续”的存储方式链表的插入和删除操作在已知位置的前提下只需要常数时间而数组扩张或中间插入动辄牵扯一整片内存。但天下没有免费的午餐。数组按下标访问是 O(1)链表要访问第 k 个节点必须从头一个节点一个节点走过去时间复杂度 O(n)。所以链表解决的痛点从来不是“查得快”而是“改得灵活、存得省力”。它适合的场景一句话就能概括读少写多、长度不确定、插入删除频繁。典型例子包括编辑器的撤销栈、操作系统的进程管理队列、浏览器的前进后退历史底层都有链表的影子。这篇文章我希望你把它当成一本“链表使用手册”来读。我会从最基础的节点结构讲起手写单链表的创建、插入、删除、查找、反转的完整代码再把双链表、循环链表和面试高频题串一遍最后把我踩过的指针和内存的坑全抖出来。不管你是考研复习数据结构、准备面试还是自己写项目要用链表按这篇文章的思路走一遍链表基本就通透了。提示链表在 C/C 里体现最直观因为指针就是链表的骨架。Python 等高级语言里也有链表实现但很多语法糖把“指针”藏起来了容易让人误以为自己懂了。所以这篇文章以 C 为主穿插 Python 的对照实现。2. 先搞懂链表的一张“广告图”节点、指针与头结点2.1 节点是怎么组成的链表的每个“积木块”叫做节点Node最简化的节点长这样一个存数据的变量一个指向下一个节点的指针。struct Node { int data; // 数据域这里以 int 为例 Node* next; // 指针域指向下一个节点 };就这么简单。数据域可以装任何类型int、string、一个结构体、甚至另一个链表都行。指针域保存的是下一个节点的地址。多个节点通过 next 串起来最后一个节点的 next 指向 nullptrC 语言里是 NULL表示链条到头了。用一张生活中常见的图类比这就好比一串挂钥匙的钥匙环每个环里套着一张小卡片写数据环上伸出一根绳子绑着下一个环。你要找第三张卡片必须从第一个环开始顺着绳子一个一个摸过去。2.2 头指针、头结点、首元结点别再混淆了这三个概念是链表入门第一个劝退点我当年也绕了整整一下午。用大白话解释头指针指向链表第一个节点的指针变量它是整个链表的“入口”。链表的操作几乎都从它开始它类似于数组的数组名。首元结点存放第一个有效数据的节点。头结点在首元结点之前额外加的一个空节点数据域可以不用也可以存链表长度之类的附加信息。它的作用是统一操作逻辑。为什么要引入头结点关键好处有两个。第一插入和删除代码不用对“第一个位置”单独做 if 判断没有头结点时在头部插入要改动头指针本身而有了头结点首元结点前面总有“一个节点”操作就统一了。第二空链表和非空链表的结构得到统一空链表也不是 nullptr 指针干戳着而是一个孤零零的头结点。不过我要说句实话头结点不是必须的。很多算法题里直接用一个 head 指针就搞定比如 LeetCode 的大部分单链表题。但如果你写工程代码或者做课程设计加头结点往往更稳。我自己的习惯是刷题用裸指针写项目用带头结点两种都得会。2.3 为什么要“动态申请”节点而不是开一个数组刚学的时候不少人会有疑问我不就是需要一个一个的节点吗直接开一个 Node 数组不就行了这确实能模拟链表但失去了链表最核心的价值——按需分配不占多余内存也不怕扩容。数组是一整块连续内存声明时必须知道大小小了不够用大了浪费。链表则是每次插入时用 newC或 mallocC动态申请一个 Node用完了用 delete 或 free 释放。内存不是连续排布的系统根据当前堆里哪有空位就放在哪所以链表能“东拼西凑”地用碎片空间。但动态申请也带来了一个大麻烦你拿到的是一块“容易丢”的内存。如果只改了指针却忘了释放旧节点内存泄漏就出现了。这个问题我会放到后面专门讲。3. 手写单链表核心操作从建表到头插尾插删除查找3.1 建表头插法和尾插法建链表最常见的有两种方式头插法和尾插法。头插法每次把新节点插到链表头部注意这样得到的链表顺序和输入顺序是反的尾插法每次挂到末尾顺序一致。#include iostream using namespace std; struct Node { int data; Node* next; Node(int val) : data(val), next(nullptr) {} }; // 头插法新节点总是成为第一个有效节点 Node* insertAtHead(Node* head, int val) { Node* newNode new Node(val); newNode-next head; // 新节点指向原来的头 head newNode; // 更新头指针 return head; } // 尾插法找到当前最后一个节点再接上新节点 Node* insertAtTail(Node* head, int val) { Node* newNode new Node(val); if (head nullptr) { return newNode; } Node* cur head; while (cur-next ! nullptr) { cur cur-next; } cur-next newNode; return head; }头插法代码比尾插法简洁但注意它的顺序反转特性这个特性在有些题目里能巧妙利用比如“反转链表”不用新建任何节点就能做到本质上就是反复头插。尾插法如果每次都从头遍历到末尾构建 n 个节点的时间复杂度是 O(n²)数据量大时非常亏。优化的惯用技巧是额外维护一个 tail 指针指向末尾每次插入直接tail-next newNode; tail newNode;这样时间复杂度降为 O(n)。3.2 指定位置插入先找到前驱链表插入的核心步骤就两句话先找到插入位置的前一个节点然后让新节点先接上后一个节点再让前一个节点指向新节点。顺序千万别反。// 在第 pos 个位置从1开始计数之后插入节点head 为头指针 Node* insertAfter(Node* head, int pos, int val) { Node* newNode new Node(val); Node* cur head; int count 1; while (cur ! nullptr count pos) { cur cur-next; count; } if (cur nullptr) { cout 位置不合法 endl; delete newNode; // 防止内存泄漏 return head; } newNode-next cur-next; // 先连后面 cur-next newNode; // 再接前面 return head; }新手最容易犯的错误是先执行cur-next newNode;把原来的后续节点丢掉了后面的链表整个断掉。记住一个口诀先接后链再改前驱。这跟插队类似——你插队得先抓住后面那个人的手再让前面的人松开他的衣角顺序反了后面那人就溜了。3.3 删除节点记住“绕过”的思想删除的核心不是真正把内存里的节点消掉而是让前一个节点跳过当前节点直接指向下一个节点再把当前节点 delete 掉。Node* deleteNode(Node* head, int val) { if (head nullptr) return nullptr; // 如果要删的是头结点 if (head-data val) { Node* temp head; head head-next; delete temp; return head; } Node* cur head; while (cur-next ! nullptr cur-next-data ! val) { cur cur-next; } if (cur-next nullptr) { cout 没找到值为 val 的节点 endl; return head; } Node* temp cur-next; cur-next temp-next; // 绕过要删的节点 delete temp; // 释放内存 return head; }删除节点最容易出的问题是什么一是没保存待删节点就改了指针导致没法 delete内存泄漏二是删掉头结点的时候忘了更新 head 指针整个链表入口丢了三是遍历时用已经释放的节点继续访问也就是“悬空指针”。这三个坑我在实际调试里见过太多次后续会专门展开。3.4 查找、遍历与修改一切的基石遍历链表的模板代码要学会“肌肉记忆”void traverse(Node* head) { Node* cur head; while (cur ! nullptr) { cout cur-data - ; cur cur-next; } cout nullptr endl; }查找某个值的节点、统计长度、修改某个节点数据都是在遍历基础上加一点点逻辑。比如查找倒数第 k 个节点可以用“双指针法”一个指针先走 k 步然后两个指针同步走当快指针走到末尾时慢指针正好指向倒数第 k 个节点。这类技巧属于链表的高频考点但核心还是遍历框架。4. 链表高频变体双链表、循环链表与几道经典必刷题4.1 双链表让回溯也成为 O(1)单链表只能往一个方向走找个前驱节点得从头再遍历一遍这在某些场景下就很浪费。双向链表Doubly Linked List给每个节点多加了一个 prev 指针指向前一个节点。struct DNode { int data; DNode* prev; DNode* next; };双向链表的好处是双向遍历、删除当前节点时不需要找前驱直接用cur-prev-next cur-next; cur-next-prev cur-prev;时间复杂度 O(1)。代价是每个节点多花一个指针的内存插入和删除时要多维护一个方向的指针代码容易写乱。工程里最常见的双链表应用就是 LRU 缓存。面试题经常要求用哈希表 双向链表实现 LRU哈希表负责 O(1) 查找双向链表负责 O(1) 移动和删除。这个题能完整写出来基本说明你对链表结构的理解到位了。4.2 循环链表最后一个节点又指回开头循环链表把最后一个节点的 next 指向头结点或者头指针整个链表变成一个环。它适合需要“无限轮转”的场景最典型的是约瑟夫环问题以及一些操作系统中的轮转调度算法。循环链表有个重要细节循环条件从判断cur ! nullptr变成判断cur ! head因为如果你还是用 nullptr 判空遍历永远不会停止直接死循环。写循环链表的时候先画一张图明确你要让循环从哪里结束再动手写代码。4.3 面试高频题反转链表、快慢指针找环、合并有序链表反转链表是我见过考频最高的一道链表题递归和迭代两种写法都要会。迭代版的核心思路就是“头插法”思想从头到尾扫一遍把每个节点拆下来怼到新链表头部Node* reverseList(Node* head) { Node* prev nullptr; Node* cur head; while (cur ! nullptr) { Node* next cur-next; // 先保存下一个节点 cur-next prev; // 反转指针 prev cur; // prev 往前推进 cur next; // cur 往前推进 } return prev; // 结束后 prev 就是新头结点 }这段代码我第一次写的时候漏了Node* next cur-next;这一行结果 cur 指向反转后下一个节点找不到了整个链表断成两截。写反转链表的重点就是一个字先备份再反转再推进。快慢指针找环也是热门题。慢指针每次走一步快指针每次走两步如果存在环快慢指针必然会相遇如果快指针遇到 nullptr说明无环。这个思路还能延伸出“寻找链表中点”“寻找倒数第 k 个节点”等方法建议把这几题放在一起刷效率很高。合并两个有序链表则是递归思想很好的练习题一句两句话讲不清但核心是每次只比较当前两个链表的头结点谁小谁就先被拿去剩下部分递归处理。链表很多递归题其实都长一个样关键是别陷入细节而是抽象出一个“当前节点 子问题”的视角。5. 写链表最容易踩的 4 个坑指针、边界、内存和死循环5.1 空指针访问最大的隐形杀手空指针访问基本排在链表 bug 榜第一名。典型场景删除节点时循环条件是while (cur-next ! nullptr cur-next-data ! val)这里要先判断cur-next ! nullptr再访问cur-next-data。如果你把判断顺序写成cur-next-data ! val cur-next ! nullptr当cur-next为 nullptr 时程序直接崩溃。C 和 C 里这叫未定义行为有的编译器闷声不响返回随机值有的直接 Segmentation Fault。写链表操作前先问自己三个问题这个指针可能为 nullptr 吗往前访问还是往后访问如果链表为空我的代码还会走通吗养成这三个习惯空指针问题能消灭八成。5.2 插入/删除时的“断链”问题上一节提到插入要先接后链删除要先保存再绕过。很多 bug 不是逻辑想不明白而是代码顺序写反了。我把正确顺序固定成两个模板背下来插入已知前驱 p新节点 s先s-next p-next;再p-next s;。删除已知前驱 p要删 q先p-next q-next;再delete q;。这个顺序写熟了链表的基本操作就稳了一半。另一个相关问题是修改指针时“丢了头结点”尤其是在头插和删除第一个节点时忘了让 head 指向新头部之后遍历就找不到链表入口了。解决方法也很朴素每次修改链表的函数返回最新的 head 指针像我们上面的写法一样。5.3 内存泄漏与悬空指针用 C/C 写链表内存管理是绕不开的。每次 new 一个节点就要确认它将来会被 delete。删除节点时如果只改了指针不delete temp内存泄漏但如果delete之后还继续用temp-next就是悬空指针访问。我在工程里见过一种很隐蔽的泄漏循环删除链表所有节点时直接把 head 往下移却不保存要删除的节点例如while (head ! nullptr) { head head-next; // 错误示范原来的头结点没人 delete }正确写法是while (head ! nullptr) { Node* temp head; head head-next; delete temp; }这个坑尤其容易出现在“清空链表”和“析构函数”里。建议写完链表类后用 Valgrind 或 AddressSanitizer 跑一遍把内存问题全暴露出来。Python、Java 这类带垃圾回收的语言没这个烦恼但理解内存分配仍然是通用素养。5.4 卷进死循环循环链表和排序里的陷阱链表出现死循环通常是两个原因一是遍历判断条件写错了while (cur ! nullptr)在循环链表里根本不生效二是插入或反转时不小心把链表改成了一个环指针转了一圈又回到原处。排查死循环有个小技巧加一个计数器循环超过一定次数就强制退出并打印当前节点地址很快能看出指针是不是绕圈了。调试链表时我强烈建议先画图把每个节点画成方块把指针画成箭头每一步操作都对照图检查这比盯着代码空想要高效十倍。6. 链表进阶心态从“看得懂”到“写得顺”的最后一公里链表入门难难在它是第一种让初学者需要“同时管理多个指针”的数据结构。数组你只需要管一个下标链表却要同时维护好几个节点的指针关系。所以当你第一次写链表代码觉得头晕完全正常。我给你一个刚练手的脚本先把单链表的创建、遍历、插入、删除四个操作不看书手写一遍用随机数据跑通然后把反转链表用迭代和递归各写一遍再把双链表的插入删除和循环链表的遍历各写一遍。这个过程大概需要两三天但完成后你会发现指针操作突然“长在脑子里了”再去看树的遍历、图的邻接表都会顺很多。有人说“链表已死”现在的高级语言有数组、列表、向量怎么都能替代。但我不这么看。操作系统内核里、Redis、文件系统、JVM 内存管理链表到处都是。更重要的是链表是“动态数据结构”的第一课它教会你用指针组织数据、管理内存、思考时间与空间的取舍这种思维方式才是数据结构真正的价值所在。最后我把最重要的经验压成一句话写链表先画图再写代码判断边界再动指针保存备份再改指向。你把这三条刻进习惯里链表这一关就过了。