单链表实战指南：从建表、插入删除到逆序与循环链表核心操作

单链表这四个字，在我接触过的所有数据结构基础内容里，属于那种“看起来最简单、上手却最容易翻车”的东西。很多初学者看完概念觉得懂了，一动手写插入和删除就晕，指针满天飞，不是断链就是死循环。作为一个常年跟链表打交道的人，今天想把这门入门课的底子完整讲透——从为什么先学单链表、带头结点和不带头结点的区别，到建表、插入、清空、循环链表、逆序这些经典操作，再到我自己调试时踩过的那些坑，一次说清楚。

这份内容适合三类人：刚开始学数据结构的学生、需要复习链表操作应对笔试的求职者，以及工作中需要手写基础结构的开发者。不管你是用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, val=0, next=None): self.val = val self.next = next

Python的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”，链表顺序随之调整。

完整流程可以拆成五步：

1. 创建新节点，分配内存并赋值。
2. 判断插入位置是否合法（pos < 1视为非法）。
3. 若不带头结点，且pos == 1，直接更新头指针。
4. 否则遍历找到前驱节点，同时判断前驱是否为空。
5. 修改指针完成插入：新节点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置为NULL：

void 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这种显式操作，但清空同样需要断开引用关系。最简单的做法是直接把头指针设为None，Python的垃圾回收会处理后续节点，因为没有任何引用指向它们了。如果你用的是循环链表，就必须先把循环断开（把链表从环打开）再置空，否则互相引用可能导致无法被回收。

3.4 遍历、查找、删除：最常用的基础操作速查表

单链表基本操作实验通常包含遍历、查找、删除、求长度、清空这些。我把高频操作的思路整理成一个速查表，方便对照：

删除操作要额外注意：删除第一个节点时，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应该停在哪个位置”没想清楚。建议用固定例子手动模拟一遍：n=5，k=2，画出每次删除前后的链表状态，很快就能理顺。

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是None，cur是头节点。循环第一步先保存cur.next到next_node，因为接下来cur.next要被改写，如果不保存，就找不到原链表的下半截了。然后让cur.next指向prev，完成当前节点的箭头反转。接着prev推进到cur，cur推进到next_node。循环结束时，cur变成None，prev指向原链表的尾节点，也就是逆序后的新头节点，所以返回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，那就埋下隐患。

排查野指针没有银弹，只能靠规范代码和工具。我自己调试链表时几乎必开AddressSanitizer（ASan），编译加-fsanitize=address，它能在你访问非法内存的第一时间报错并指出是哪一行。新手用这个工具能节约大量排查时间，比盯着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 面试和实验里最值得关注的细节清单

根据我带学生和看候选人做题的经验，我总结了一份高频扣分点和问法，方便你在实验和面试前自查：

面试里关于单链表的问法，除了逆序和环检测，还经常考“删除倒数第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的来源。入门阶段写代码慢一点没关系，但每写一个指针赋值都要能说出来“我现在让谁指向谁，原来的那个引用还有没有人保存”。只要养成这个习惯，单链表对你来说就不再是一个记不住的代码模板，而是一种真正能自己推导的数据结构。

这些年带过的人里，凡是能在一周内把这个基础吃透的，后面学双向链表、栈、队列都会顺很多。如果你在练习时遇到某个操作卡住，最好的方式不是继续硬想，而是把链表画在纸上，拿笔模拟指针的移动，一遍不行就两遍。这种手绘模拟带来的直觉，比任何视频教程都扎实。