单链表这四个字在我接触过的所有数据结构基础内容里属于那种“看起来最简单、上手却最容易翻车”的东西。很多初学者看完概念觉得懂了一动手写插入和删除就晕指针满天飞不是断链就是死循环。作为一个常年跟链表打交道的人今天想把这门入门课的底子完整讲透——从为什么先学单链表、带头结点和不带头结点的区别到建表、插入、清空、循环链表、逆序这些经典操作再到我自己调试时踩过的那些坑一次说清楚。这份内容适合三类人刚开始学数据结构的学生、需要复习链表操作应对笔试的求职者以及工作中需要手写基础结构的开发者。不管你是用C、C还是Python核心思想完全通用代码我会用C和Python分别演示方便你对照理解。1. 站在实用角度重新认识单链表1.1 为什么入门数据结构总和数组比对着讲数组和链表是线性表的两种存储方式教材里几乎都会拿它们做对比。数组在内存里是一块连续空间通过下标访问能做到O(1)随机访问链表则用零散的内存块拼接逻辑上的顺序每个节点除了存数据还得存一个指向下一个节点的指针或者引用。数组的优势是访问快、占用额外空间少但瓶颈也明显插入和删除需要搬动大量元素最坏情况是O(n)数组大小一旦定下来扩容就得重新申请整块内存再拷贝代价高。链表恰恰相反插入和删除只需要修改指针理想情况下O(1)长度也可以动态变化但随机访问必须从头遍历。生活类比数组像电影院连排座位找13号座位直接按座位号走过去就行但中间加个人所有人都得挪一挪链表像放学排队每个人只记住身后的同学是谁想找第13个人得从头一个个问过去但队伍中间加个人只需要前面那人改一下指向就行后面不用动。这就是单链表存在的核心价值它适合频繁插入删除、数据量不确定的场景。学链表的关键不是背代码而是建立“用指针连接记忆块”的空间直觉。1.2 单链表的“积木块”节点到底怎么定义单链表的最小单位是节点。每个节点包含两部分数据域和指针域。数据域可以是整数、字符串、结构体等任意类型指针域在单链表中只存一个next指针指向后继节点。C语言里的经典定义长这样typedef struct Node { int data; // 数据域 struct Node *next; // 指针域指向下一个节点 } Node;注意C语言的结构体定义里必须有struct Node *next这里不能写成Node *next因为在结构体还没定义完整时Node这个别名还不存在。这一点很多新手第一次写都会报错。Python里则是用类来实现class ListNode: def __init__(self, val0, nextNone): self.val val self.next nextPython的next默认值是None正好用来表示链表末尾。C语言里则习惯用NULL表示空指针。我建议你无论最终用哪种语言都用“画盒子”的方式先在纸上把链表画出来。每个节点画成一个方框左边写数据右边画一个指向下一节点的箭头。你会发现后面所有指针操作本质上只是改变这些箭头的指向。2. 入门第一个岔路口带头结点还是不带头结点2.1 两者的本质区别和取舍逻辑这个问题几乎是每个初学者都会遇到的困惑有的教材定义链表时有一个头结点head节点数据域不放有效数据有的教材直接让头指针指向第一个有效节点头结点都不存在。两种做法都对但代码复杂度完全不同。带头结点的好处是统一操作逻辑。头结点永远存在空链表也至少有一个节点。这样一来在头部插入新节点、在任意位置删除节点不需要专门为“插入到空表”或“删除第一个节点”做特判。所有的插入和删除可以先统一找到目标位置的前驱节点再修改指针。不带头结点则更贴近“链表本来面目”但要处理大量边界情况空表插入时头指针本身要更新删除第一个节点时头指针也要更新。这些特判写多了就乱乱就容易断链。所以我的建议很直接如果自己实现练手用不带头结点感受一次完整边界处理能极大提升对指针的理解如果是做工程、考试或比赛默认带头结点逻辑更干净。2.2 不带头结点的单链表插入到底要怎么特判以“在指定位置插入”为例。假定链表的头指针是head要在第pos个位置插入新节点newNode位置编号从1开始。不带头结点时必须分两种情况第一种插入位置是1即新的节点将成为第一个节点newNode-next head; head newNode; // 头指针必须更新第二种插入位置大于1需要找到第pos-1个节点作为前驱然后插入Node *p head; for (int i 1; i pos - 1 p ! NULL; i) { p p-next; } if (p NULL) { // 位置无效 return; } newNode-next p-next; p-next newNode;这段代码里最容易写错的是p NULL的判断。一旦插入位置超过链表长度遍历会走到链表末尾的NULL这时如果继续p-next就是对空指针操作程序直接崩。所以每写一个指针操作先问自己这个指针在下一次被解引用时有没有可能已经是NULL了。Python版本同样处理def insert(head, pos, val): node ListNode(val) if pos 1: node.next head return node p head for _ in range(pos - 2): if p is None: return head p p.next if p is None: return head node.next p.next p.next node return head注意Python里操作单链表返回值很重要因为头指针可能改变。C语言可以传二级指针Node **head来修改头指针Python则需要让函数把新头返回否则调用方拿到的还是旧链表。2.3 带头结点是怎么把特判消灭掉的带头结点之后头指针head永远指向那个哑节点dummy node真正的数据节点从head-next开始。插入位置编号我们约定从1开始也是第一个数据节点那么无论插入到第1个还是第n个代码统一为Node *p head; // 从头结点开始 for (int i 1; i pos p ! NULL; i) { p p-next; } if (p NULL) return; newNode-next p-next; p-next newNode;细品一下因为头结点存在即使插入位置是1前驱也不是NULL而是头结点本身。于是那段对“空表为何都能插入”的困惑就消失了空表时head-next是NULL新节点接上去链表非空逻辑依然统一。这就是为什么很多竞赛代码和源码实现里会故意创建一个哑头节点。它多占一个节点空间但换来的是少写大量if减少出bug概率。工程上的“额外抽象”常常就是这个意思。3. 单链表的基本操作实验建表、指定位置插入、清空3.1 两种建表方式头插法和尾插法建表是最常见的实验内容。头插法每次把新节点插到链表头部插入顺序和最终链表顺序相反。例如依次输入1、2、3最终链表是3、2、1。Node *createByHead(int arr[], int n) { Node *head NULL; for (int i 0; i n; i) { Node *node (Node *)malloc(sizeof(Node)); node-data arr[i]; node-next head; head node; } return head; }尾插法则需要额外维护一个尾指针tail每次把新节点挂在尾巴后面。这种建表方式保持了输入顺序更符合直觉Node *createByTail(int arr[], int n) { Node *head NULL, *tail NULL; for (int i 0; i n; i) { Node *node (Node *)malloc(sizeof(Node)); node-data arr[i]; node-next NULL; if (head NULL) { head tail node; } else { tail-next node; tail node; } } return head; }尾插法里最容易犯的错误是忘了把tail-next指向NULL。如果最后一个节点没有把next置空后续遍历会直接越界。我见过不少实验报告建表时循环里只赋值数据不处理next结果打印链表时输出一串乱码其实就是这个原因。3.2 在指定位置插入建立单链表的完整流程“在指定位置插入建立单链表”是热词里出现次数很高的实验题它的意思通常不是一次建完整个表而是边读取数据边把节点插入到指定编号。比如输入“在第3个位置插入值5”链表顺序随之调整。完整流程可以拆成五步创建新节点分配内存并赋值。判断插入位置是否合法pos 1视为非法。若不带头结点且pos 1直接更新头指针。否则遍历找到前驱节点同时判断前驱是否为空。修改指针完成插入新节点next指向前驱的next前驱的next指向新节点。第二步和第四步特别重要合法的判定缺一不可。比如链表长度为5用户要在第100个位置插入遍历最终p会停在最后一个有效节点此时p不为空但它后面没有第99个位置。规范做法是遍历时同时记录经过的节点个数如果实际节点数小于pos-1就视为非法。C语言里的实现可以写成int insertAtPos(Node **head, int pos, int val) { if (pos 1) return 0; Node *newNode (Node *)malloc(sizeof(Node)); newNode-data val; newNode-next NULL; if (pos 1) { newNode-next *head; *head newNode; return 1; } Node *p *head; int count 1; while (p ! NULL count pos - 1) { p p-next; count; } if (p NULL) { free(newNode); // 插入失败要释放内存 return 0; } newNode-next p-next; p-next newNode; return 1; }这里我特意free(newNode)了因为位置非法时节点不接入链表如果不释放就是一次内存泄漏。C语言操作链表要养成“节点要么在链表里要么被释放”的思维。3.3 单链表的清空到底清了什么单链表的清空也是一个实验必做题但很多人理解有偏差。清空和销毁不一样。清空是保留链表头节点如果带头结点释放掉所有数据节点销毁则是连头节点一起释放头指针置空。不带头结点时清空就是遍历所有节点逐个free最后把head置为NULLvoid clearList(Node **head) { Node *p *head; while (p ! NULL) { Node *tmp p; p p-next; free(tmp); } *head NULL; }这里最关键的一点是必须先保存next再free当前节点。否则你free掉当前节点后再通过p-next访问就已经是野指针了。很多段错误就是这么来的。为什么不能直接free(head)因为链表后面还有一长串节点只释放头节点会导致剩下所有节点无法访问形成内存泄漏。必须遍历到最后一个节点为止。Python里虽然没有free这种显式操作但清空同样需要断开引用关系。最简单的做法是直接把头指针设为NonePython的垃圾回收会处理后续节点因为没有任何引用指向它们了。如果你用的是循环链表就必须先把循环断开把链表从环打开再置空否则互相引用可能导致无法被回收。3.4 遍历、查找、删除最常用的基础操作速查表单链表基本操作实验通常包含遍历、查找、删除、求长度、清空这些。我把高频操作的思路整理成一个速查表方便对照操作核心思路复杂度关键注意点遍历打印从头指针开始逐个节点访问dataO(n)循环条件判断当前节点是否为空按值查找遍历比较data返回第一个匹配节点O(n)注意是否要找所有匹配项按位置查找遍历pos-1次返回节点O(n)位置从1开始越界判断头插新节点next指向原头更新头指针O(1)不带头结点时需二级指针或返回值尾插找到尾节点接上新节点O(n)可维护尾指针优化为O(1)任意位置插入遍历找到前驱改两个指针O(n)前驱为空则位置非法删除任意位置找到前驱绕过待删节点O(n)释放待删节点内存清空逐个释放节点头指针置空O(n)先保存next再free求长度遍历计数O(n)空表返回0删除操作要额外注意删除第一个节点时head要更新为head-next删除中间节点时前驱的next直接指向待删节点的next。两种情况都得在释放内存之前把需要保存的信息保存好。4. 循环单链表让链表的尾巴咬住头4.1 循环单链表解决什么问题普通单链表的尾节点的next是NULL遍历到底就停了。循环单链表把这个NULL改成指向第一个节点或头结点整个链表首尾相连成环。这样带来的好处是从任意一个节点出发都能遍历到所有节点不需要知道头在哪里。生活类比普通单链表像单向的逛街路线走到尽头就得掉头循环单链表像绕圈跑操无论你从哪个位置看都能顺着队伍看到所有人最后还会绕回起点。经典场景是约瑟夫环问题一群人围成一圈报数报到某个数的人出列然后从下一个人继续报数直到最后剩下一个人。这个“围成一圈”的天然结构用循环单链表表达比数组直观得多。另一个常见场景是操作系统里的进程调度轮转、任务队列循环复用。4.2 循环单链表的构建与基本操作构建循环单链表时尾节点不能指向NULL而要指向头节点。如果是不带头结点的版本尾节点的next要指向第一个有效节点Node *createCircular(int arr[], int n) { if (n 0) return NULL; Node *head NULL, *tail NULL; for (int i 0; i n; i) { Node *node (Node *)malloc(sizeof(Node)); node-data arr[i]; node-next NULL; if (head NULL) { head tail node; } else { tail-next node; tail node; } } tail-next head; // 关键一步闭合环 return head; }遍历循环链表时终止条件不能再用p ! NULL而要用p ! head并且还需要一个起始标记防止循环无限跑。常用写法是if (head NULL) return; Node *p head; do { printf(%d , p-data); p p-next; } while (p ! head);这里的do-while很关键先访问头节点再判断是否回到起点。如果用while (p ! head)开头就进不了循环了因为初始p就是head。这种小而隐蔽的边界正好是实验最容易扣分的地方。4.3 约瑟夫环循环单链表最经典的实战约瑟夫环题目描述大约是这样n个人编号1到n围成一圈从编号1开始报数每次报到k的人退出圈子接着从下一个人重新从1报数求最后留下的人的编号。用循环单链表的做法很清晰。首先构建环形链表然后从head开始数k-1步找到待删除节点的前驱因为报数到k时待删除节点就是第k个删除它并让当前节点变成它下一个节点继续循环直到链表只剩一个节点。核心删除片段Node *prev head; // 找到待删除节点的前驱需要数 k-1 步 for (int i 1; i k - 1; i) { prev prev-next; } Node *cur prev-next; printf(%d , cur-data); prev-next cur-next; free(cur); // 下一次从被删除节点的下一个节点开始报数 head prev-next;这里最坑的是循环结束条件的判断当循环链表只剩一个节点时它的next指向自己也就是head-next head此时直接输出并结束不能再用一般删除逻辑。如果没做这个判断程序会陷入死循环或者free掉已经被free的内存。我自己讲课时的体验是约瑟夫环这道题能立刻检验你有没有真正理解循环链表的指针走向。很多人写出来能跑对示例但稍微改一下k和n就出错本质还是对“前驱指针prev应该停在哪个位置”没想清楚。建议用固定例子手动模拟一遍n5k2画出每次删除前后的链表状态很快就能理顺。5. Python版经典练习单链表逆序5.1 逆序到底逆的是什么单链表逆序是热词高频词也是面试手写题里的老面孔。任务是让链表从head到尾部的方向反转比如1→2→3→4变成4→3→2→1。注意逆序不能靠新建一个临时数组把数据倒过来再填回去那样虽然结果对但空间复杂度是O(n)而且完全没考察到链表指针操作。正确的做法是原地修改指针让每个节点的next指向前一个节点。因为单链表每个节点只有指向后继的指针没有指向前驱的指针所以逆序时必须同时记住前一个节点、当前节点和后一个节点。这个思想是三指针法也是最容易理解的方法。5.2 迭代法逆序三指针走天下Python代码非常简洁def reverse_list(head): prev None cur head while cur is not None: next_node cur.next cur.next prev prev cur cur next_node return prev逐行讲解一下。初始时prev是Nonecur是头节点。循环第一步先保存cur.next到next_node因为接下来cur.next要被改写如果不保存就找不到原链表的下半截了。然后让cur.next指向prev完成当前节点的箭头反转。接着prev推进到curcur推进到next_node。循环结束时cur变成Noneprev指向原链表的尾节点也就是逆序后的新头节点所以返回prev。这里最容易犯的错误是把cur cur.next写在cur.next prev之前或者忘记先保存next。一旦忘记cur的旧的next已经被覆盖链表彻底断掉后面全是None。调试时看到输出只有两个节点然后又变None基本都是这个原因。5.3 递归法逆序代码更短理解更难递归版本在LeetCode上流行的写法是def reverse_list_recursive(head): if head is None or head.next is None: return head new_head reverse_list_recursive(head.next) head.next.next head head.next None return new_head这个递归的思想是先递归反转整个链表从head.next开始的子链表反转完成后new_head就是这个子链表的新头在原始链表中它是尾节点。此时原本的子链表头head.next变成了子链表的尾节点但它的next还是指向原链表的后续不对这里的细节是递归函数返回后head.next这个节点在反转后的子链表中已经是尾节点而且它的next指向None因为递归最后一层设置过。所以我们要做的是把head接到它后面head.next.next head也就是原来head后面的那个节点它的next指向head完成逆序的连接最后再把head.next置为None让head成为新链表的尾。递归版本适合用来加深理解但有些坑链表很长时递归深度可能爆栈面试时如果被要求O(1)空间迭代法更稳。我个人的经验是递归写起来很酷但你要能清楚解释每一步在干什么如果解释不清面试官反而觉得你是背的。能画图讲明白迭代法往往更加分。5.2和5.3之间需要小结一下。逆序还有一种变体是“反转前n个节点”和“反转区间[m, n]”基本思路一样只是要处理断开和重新拼接的边界这里不展开但它能帮你举一反三。6. 常见问题与调试记录从实验室踩坑到面试手撕6.1 为什么我的链表打印出来总串行最典型的串行现象是打印结果和预期顺序不一致或者出现无限重复的某个值。先说顺序不一致多半是用头插法建表却以为顺序没变。头插法最终链表的顺序是输入顺序的逆序这不是bug是特性。如果你想要顺序一致用尾插法。再说无限重复某个值这往往是链表中产生了环。比如某次插入时不小心让一个节点的next指向了它自己或者尾节点的next没有被置为NULL而是残留了一个旧地址遍历就会陷入死循环。排查方法很简单写一个检测环的函数用快慢指针快指针每次走两步慢指针每次走一步如果两者相遇说明有环。这本身也是一道经典链表题叫判断链表中是否有环。6.2 空指针和野指针链表程序崩溃的头号原因C语言里空指针解引用直接Segmentation Fault野指针更隐蔽它指向的内存可能已经释放但内容还没被覆盖看起来好像能读出数据时好时坏非常坑。最常见的野指针场景是use-after-free也就是先free了一个节点后面还在用它的next。前面清空链表时我先保存了p-next再free就是为了避免这个。另一个场景是函数内部新建了局部指针指向链表函数返回后局部指针本身不生效但如果你把局部指针赋值给了链表节点里的next那就埋下隐患。排查野指针没有银弹只能靠规范代码和工具。我自己调试链表时几乎必开AddressSanitizerASan编译加-fsanitizeaddress它能在你访问非法内存的第一时间报错并指出是哪一行。新手用这个工具能节约大量排查时间比盯着printf输出猜快得多。6.3 插入和删除漏了改返回值的坑在Python里写链表操作特别容易漏掉头指针更新。比如def insert(head, pos, val): ... if pos 1: node.next head return node ...但如果调用写成insert(head, 1, 99)而不用返回值head依然指向旧头新节点就“丢失”了。所以Python操作链表时函数返回值一定要接住或者把链表封装成类用类的成员变量维护head。C语言则建议用二级指针Node **head或者用一个链表结构体包含头指针。6.4 面试和实验里最值得关注的细节清单根据我带学生和看候选人做题的经验我总结了一份高频扣分点和问法方便你在实验和面试前自查常见错误错误原因正确做法插入中忘记更新头指针头插、首节点删除时头变了用二级指针或返回新头遍历循环条件写成while(p-next)少访问最后一个节点判断当前节点本身是否为空先释放再访问next野指针先保存next再free循环链表遍历无终止条件死循环do-while加回到头结点的判断删除节点后未释放内存内存泄漏在C中freePython交给GC插入位置判断只做半套越界访问同时判断位置合法性与前驱是否为空面试里关于单链表的问法除了逆序和环检测还经常考“删除倒数第k个节点”“合并两个有序链表”“找链表中间节点”。这些题都是后面内容的基础但它们的核心操作仍然是遍历、指针修改和边界处理单链表入门阶段把基础打牢后面的复杂题就是换汤不换药。6.5 调试单链表的小工具技巧写链表调试我建议你打印辅助函数一步到位直接输出完整链表状态而不是到处插printf。C语言可以写一个printList函数Python里则可以打印成类似1 - 2 - 3 - None的字符串方便直观比对预期结果。例如Python调试函数def print_list(head): values [] cur head while cur is not None: values.append(str(cur.val)) cur cur.next values.append(None) print( - .join(values))然后在测试用例里每执行完一次插入删除就打印一次配合手动画图很快能定位到问题。调试链表最忌讳的就是一段代码改来改去不打印全靠猜。我自己刷题时常用一个小技巧在关键指针操作前后各打一行比如print(before: prev, prev.val if prev else None, cur, cur.val if cur else None)特别适合排查逆序和反转区间这类操作。6.6 一步到位写链表代码前的三个自检问题每次动手写链表操作前我习惯先问自己三个问题第一这个操作会不会改变头指针如果会我有没有正确的更新机制 第二代码里所有解引用指针的地方有没有可能是空如果要遍历到指定位置位置合法吗 第三修改指针时有没有先把后续要用的节点地址保存下来会不会覆盖掉还没用到的next这三个问题能覆盖绝大多数链表bug的来源。入门阶段写代码慢一点没关系但每写一个指针赋值都要能说出来“我现在让谁指向谁原来的那个引用还有没有人保存”。只要养成这个习惯单链表对你来说就不再是一个记不住的代码模板而是一种真正能自己推导的数据结构。这些年带过的人里凡是能在一周内把这个基础吃透的后面学双向链表、栈、队列都会顺很多。如果你在练习时遇到某个操作卡住最好的方式不是继续硬想而是把链表画在纸上拿笔模拟指针的移动一遍不行就两遍。这种手绘模拟带来的直觉比任何视频教程都扎实。