单链表基础操作全解析：建表、插入删除、逆置与循环链表

单链表这一块，几乎是所有学数据结构的人绕不过去的坎。我记得当年做“单链表的基本操作实验”时，代码写得稀碎，调试全靠往控制台疯狂打印，最后才发现问题不是出在指针上，而是出在我根本没搞懂“带头结点”和“不带头结点”的区别。这篇文章就把链表里最常见的那几个操作——建表、遍历、插入、删除、清空、逆置、循环链表——从头到尾梳理一遍，代码用C语言风格和Python风格交替着给，毕竟现在不少学校的数据结构课用C，但很多自学者和转码选手是从Python入门的，两种都得能看懂。

不管你是准备数据结构期末考试、刷算法题，还是工作中真的要手写一个链表，这篇都适合。我会把每一步背后的“为什么”也讲清楚，而不是丢一堆代码让你背。

1. 链表这个数据结构，到底在用什么姿势解决什么问题

1.1 数组做不到的事，链表凭什么做到

聊链表之前，先得说清楚数组的尴尬。数组在内存里是一段连续空间，访问第i个元素是O(1)的功夫，直接拿首地址加偏移量就算出来了。但连续空间也意味着两个麻烦：第一，你在中间插入或删除一个元素，后面所有元素都得往后挪或者往前挪，平均O(n)的开销；第二，数组的容量是固定的，想要扩容，得重新找一块更大的连续内存，再把老数据复制过去。

链表解决的就是这两个问题。它的核心思想是把数据存在一个个独立的节点里，每个节点除了存自己的数据，还存一个指向下一个节点的指针。节点不要求内存连续，散落在哪里都行，只要顺着指针走，就能从一个节点摸到下一个节点。插入和删除只需要改动相邻节点的指针指向，不用搬动其他数据，这才是链表存在的真正意义。

但你要记住一句话：链表是用“访问变慢”换“插入删除变快”。数组可以O(1)随机访问任意位置，链表不行，你想找第n个节点，只能从表头一个一个next过去，是O(n)。所以实际工程项目里，如果主要是读操作、按索引访问，多数人用动态数组（C++的vector，Python的list）；如果主要是高频的插入删除操作，才轮到链表上场。

1.2 带头结点和不带头结点，看似只差一个指针

这是新手第一个崩溃点。很多教材一开始讲“不带头结点的单链表”，然后练习题又全是带头结点的，学生直接懵了。区别其实很小，但影响很大。

不带头结点的链表，头指针直接指向第一个数据节点。当链表为空时，头指针是NULL。当你需要在表头插入一个节点时，你得修改头指针本身，所以函数的参数必须是指针的指针（C语言里是LNode **L，C++里用引用&L也行），否则你在函数里把头指针改了，传出去后主调方还是老样子。

带头结点的链表，有一个额外的头节点在链表最前面，头节点的数据域通常不用，指针域指向第一个真正的数据节点。这样一来，哪怕链表是空的，头指针也不为NULL，它指向那个头节点。插入、删除第一个数据节点时，操作方式和其他位置完全一样，不需要特殊处理头指针。这个设计减少了大量边界判断，代码写起来舒服得多。

如果你只是想理解概念，我把话说直白点：带头结点就是一个“哨兵”，它让你不用在“第一个位置”和“其他位置”之间来回切逻辑。我个人做实验、做算法题，只要不是题目明确要求不带头结点，一律带头结点，省心。

2. 建立单链表：头插法、尾插法、以及你该选谁

2.1 头插法和尾插法的代码对比

建立单链表最常用的两种方法就是头插法和尾插法，名字很直白：新节点插在头还是插在尾。

头插法实现简单，逻辑是每来一个新节点，就让它成为新的第一个数据节点——新节点的next指向原来的第一个数据节点，然后让头节点的next指向新节点。代码大概是这个样子：

#include <stdio.h> #include <stdlib.h> typedef struct LNode { int data; struct LNode *next; } LNode; LNode* createByHeadInsert(int arr[], int n) { LNode *head = (LNode*)malloc(sizeof(LNode)); head->next = NULL; for (int i = 0; i < n; i++) { LNode *newNode = (LNode*)malloc(sizeof(LNode)); newNode->data = arr[i]; newNode->next = head->next; head->next = newNode; } return head; }

注意头插法有一个副作用：它会把输入顺序反过来。比如你按1、2、3的顺序插入，最后链表里实际是3、2、1。这在某些场景下是好用的（比如从键盘读入一串数，想逆序存储），但如果你想做的是“按输入顺序复制一份链表”，头插法就直接翻车了。

尾插法就直白得多，新节点每次都接到链表末尾。但尾插法需要一个额外的指针持续记录当前的“尾节点”，不然你每次都得从头遍历到尾部，建一个n长度的链表就退化成O(n²)了。常规写法如下：

LNode* createByTailInsert(int arr[], int n) { LNode *head = (LNode*)malloc(sizeof(LNode)); head->next = NULL; LNode *tail = head; for (int i = 0; i < n; i++) { LNode *newNode = (LNode*)malloc(sizeof(LNode)); newNode->data = arr[i]; newNode->next = NULL; tail->next = newNode; tail = newNode; } return head; }

这个tail = tail->next的更新很容易漏。我见过很多初学者写完插入之后发现链表只有一个节点，就是因为忘了移动尾指针。养成习惯：尾指针不移动，尾插法就是假的尾插法。

2.2 循环单链表的建立与判断

循环单链表是在单链表的基础上，把最后一个节点的next指针从NULL改成指向第一个节点（如果带头结点，就指向头节点；如果不带头结点，就指向第一个数据节点）。

循环链表解决了什么问题？最主要的是从任意节点出发都能遍历到整张表。单链表你想从头走一遍还好，但如果拿着某个节点的指针，想回到头节点，单链表做不到，循环链表可以一路next绕回来。

建立循环链表的时候，尾插法的改动极小，只需要在最后把tail->next重新指向head：

LNode* createCircularList(int arr[], int n) { LNode *head = (LNode*)malloc(sizeof(LNode)); head->next = NULL; LNode *tail = head; for (int i = 0; i < n; i++) { LNode *newNode = (LNode*)malloc(sizeof(LNode)); newNode->data = arr[i]; newNode->next = NULL; tail->next = newNode; tail = newNode; } tail->next = head; // 首尾相接 return head; }

判断一个链表是不是循环链表，最朴素的办法是：设一个指针从head开始绕圈，复杂度是O(n)，但你要注意别死循环，一定要记录走过了多少个节点，或者判断指针是否回到了head。更经典的方案是两个指针一快一慢，快指针每次走两步，慢指针每次走一步，如果链表中存在环，这两个指针迟早会相遇。这个思路在算法题里叫快慢指针，也用来判断普通链表中是否存在环。

顺带说一句，遍历循环链表的终止条件不能写p == NULL了，而要写p == head（带头结点）或者p == 第一个节点，用do...while结构会更顺手，否则第一次循环就退出了。

3. 指定位置插入与删除：先把“位置”这个坑说清楚

3.1 指定位置插入的完整步骤

“把节点插到第i个位置”这句话，在代码里必须非常精确，因为“位置”的定义每个题都不一样。有的题目里“位置1”指的是第一个数据节点，有的题目里“位置0”才算第一个。教材里通常约定：带头结点的单链表，第i个位置是指从头节点后面数，第1个数据节点为首元节点。插入算法核心是：先找到第i-1个节点，也就是待插入位置的前驱节点，然后执行插队动作。

为什么必须先拿到前驱节点？因为单链表只能单向走，你手里只有当前节点的指针，如果当前节点就是第i个节点，你根本不知道第i-1个节点在哪，没法把它的next改为指向新节点。所以单链表的插入操作，本质上仍然是“找位置”O(n)的开销，只有真正改指针的那两行是O(1)。

int insertByIndex(LNode *head, int i, int value) { // head是带头结点的头指针，i从1开始 LNode *p = head; int j = 0; while (p != NULL && j < i - 1) { p = p->next; j++; } if (p == NULL) { return -1; // 位置非法 } LNode *newNode = (LNode*)malloc(sizeof(LNode)); newNode->data = value; newNode->next = p->next; p->next = newNode; return 0; }

这里有个顺序陷阱：必须先执行newNode->next = p->next，再执行p->next = newNode。你要是反过来写，先把p->next改成newNode，那么原来的下一个节点就找不到了，链就断了。我记得大学实验课上老师反复强调这一句，但每次总有人踩。

位置合法性也要搞清。假设链表有n个数据节点，插入位置i可以是1到n+1，因为允许插在末尾。如果你循环结束后p是NULL，说明传入的i太大或者太小，直接返回错误即可，不用硬插。

3.2 边界条件与删除的联动

删除第i个节点同样是先找前驱。找到第i-1个节点后，要被删的节点是p->next，然后让p->next = p->next->next，跳过去。别忘了free掉删除的节点，C语言里不free就内存泄漏，实验课的检测工具经常会对着一堆泄漏报告打红叉。

另外，很多人不知道“按值删除”和“按位置删除”在思路上是有区别的。按位置删除，遍历计数就行；按值删除，要拿目标值和节点里的data做比较，可能还要处理“重复值删第一个还是删全部”的需求。这在题目里通常有明确要求，写代码前先看清楚。

边界条件总结成一张表，写代码之前对着看一遍，基本能避开90%的坑：

如果你用的是不带头结点的链表，删除第一个节点时还得改头指针本身，代码里就会多一层判断：if (head->data == target) { head = head->next; }。这也是我推荐带头结点的原因之一，逻辑分支少了，出错概率自然小。

4. 遍历、清空、逆置：三个最容易被代码面试考到的操作

4.1 遍历的几种形态

链表遍历听着简单，但至少有三种形态要分清楚：打印全部节点、统计节点个数、以及“遍历+条件判断”的变体。基本逻辑都长一个样：

void traverse(LNode *head) { LNode *p = head->next; while (p != NULL) { printf("%d ", p->data); p = p->next; } printf("\n"); }

递归遍历也是链表题目里常考的花活。链表天然适合递归，因为“访问当前节点，然后处理剩余部分”就是递归结构。比如递归打印链表：

void traverseRecursive(LNode *p) { if (p == NULL) return; printf("%d ", p->data); traverseRecursive(p->next); }

递归版本代码很漂亮，但实际工程里要小心：链表长到几万个节点，递归深度跟着上去了，栈溢出风险很大。我倾向的说法是：面试里你写出递归说明你理解了结构，工程上老老实实写循环。

还有一种遍历是高频率出现的——查找第k个节点。很多题目会包装成“输出倒数第k个节点”，那就不需要先遍历一遍求长度再走一遍，直接用双指针：一个先走k步，然后两个指针同步前进，先走到底，后面的指针恰好停在倒数第k个节点。

4.2 单链表的清空与内存释放

清空链表和删除链表是两个操作，很多人混在一起。清空是保留头节点，把数据节点全部删掉；销毁链表是连头节点一起释放，头指针置为NULL。

清空的核心不是把指针断开就完事，每一个malloc出来的节点都必须free，不free就是内存泄漏。正确的清空方式是边遍历边释放：

void clearList(LNode *head) { if (head == NULL) return; LNode *p = head->next; while (p != NULL) { LNode *temp = p; p = p->next; free(temp); } head->next = NULL; }

注意这里必须先把p = p->next存下来，再去free(p)。你要是先free了p，再访问p->next，就是典型的悬空指针，程序可能当场崩溃，也可能“运气好”继续跑，跑到某一步莫名出错。C语言调试里这类问题最恶心，因为它不稳定复现。

清完以后别忘了head->next = NULL，不然head还指向一块已经free掉的内存，后面遍历直接访问野指针。这个习惯应该像刻在肌肉里一样。

4.3 逆置链表的迭代法与递归法

链表逆置是面试和期末考的重灾区，看着不难，但手写容易乱。迭代法需要三个指针：pre、cur、next。思路是遍历链表，把每个节点的next指向前一个节点，然后把pre和cur整体后移。文字描述很绕，直接看代码更清楚：

LNode* reverseList(LNode *head) { // 传入带头结点的链表，返回逆置后的新头指针 LNode *pre = NULL; LNode *cur = head->next; while (cur != NULL) { LNode *next = cur->next; cur->next = pre; pre = cur; cur = next; } head->next = pre; return head; }

我自己记这段代码的口诀是：先存next，再扭cur，然后pre和cur各进一步。三个指针缺一不可，少一个都会丢链。

递归法逆置的思路是“假定子链表已经逆置好了，再把头节点接到末尾”。C代码看起来短，理解起来确实需要一点递归直觉：

LNode* reverseRecursive(LNode *node) { if (node == NULL || node->next == NULL) return node; LNode *newHead = reverseRecursive(node->next); node->next->next = node; node->next = NULL; return newHead; }

重点在于倒数两行：node->next->next = node的意思是把下一个节点的next指回来，等于把当前节点挪到逆置后子链表的末尾；node->next = NULL是斩断原来的正向连接，避免环。假如你递归到第k层，第k+1层已经帮你把后面的链表逆好了，你现在只需要处理当前节点和下一个节点这两个的关系，整体就拼起来了。

提示：逆置操作在工程里用得不多，但在算法题里几乎是必考之一，刷题练习时建议迭代法和递归法都写一遍，写到不用思考肌肉记忆为止。

5. 双链表：当你想往回走的时候

5.1 双向链表的基本结构和插入删除差异

单链表的痛点很明确：只能从前往后走，想找前驱节点只能重新从头遍历。双向链表就是在这个缺陷上修的——每个节点除了data和next，还多一个prior指针指向它的前驱。代价是每个节点多占一个指针的空间。

双向链表里的插入操作，单看指针改动数量就比单链表多一倍。比如在p节点之后插入新节点s：

s->prior = p; s->next = p->next; if (p->next != NULL) { p->next->prior = s; } p->next = s;

很多人写这里会把p->next->prior = s给丢了，结果next方向接上了，prior方向没接上，遍历一往回走就断。

删除操作同样多一步。删除p节点的标准做法：

p->prior->next = p->next; if (p->next != NULL) { p->next->prior = p->prior; } free(p);

这里多了一个if判断，因为如果p是最后一个节点，p->next是NULL，直接访问p->next->prior就是在给NULL写东西。这种边界判断不是“为了严谨而严谨”，是真的会崩。

5.2 循环双链表与工程中的取舍

把双向链表的头节点和尾节点用两个方向的指针连起来，就是循环双链表。这种结构的最大好处是：从任何一个节点出发，向前向后都能遍历到所有节点，查找效率在某些场景下有明显提升。

大名鼎鼎的LRU缓存淘汰算法，底层用的就是双向链表加哈希表。为什么是双向链表而不是单链表？因为LRU里经常需要把某个节点从中间移动到头部，如果你用单链表，删除这个中间节点时需要找到它前驱，那就得从头遍历，O(n)直接打穿整个缓存的性能目标。双向链表给了你前驱信息，删除和移动都是O(1)。

工程上还有一个很务实的取舍：链表节点是散落在不同内存地址的，对CPU缓存不够友好。数组在内存里是连续的，遍历时预取缓存，效率极高；链表的next指针到处乱跳，你访问完一个节点，下一个节点大概率不在当前缓存行里，只能等内存加载。所以在追求极致性能的高频遍历场景，别为了“链表听起来很酷”而用链表。真需要频繁插入删除，也可以考虑跳表、B树这类更复杂的结构，或者直接用语言内置的容器，比如Python的list虽然是动态数组，但它在内存里连续，实际使用中插入删除的性能表现常常比你想的好，因为它是C实现的，常数极小。

6. 语言之争：C/C++结构体链表与Python链表的语法差异

6.1 C/C++结构体链表基本语法

C语言里链表的所有基础都是结构体和指针。定义节点的标准姿势：

struct ListNode { int val; // 数据域，可以根据需求换成其他类型 struct ListNode *next; // 指针域 };

C语言里还有一个常见坑：typedef struct ListNode和struct ListNode的关系。很多教材喜欢这样写：

typedef struct LNode { int data; struct LNode *next; } LNode;

这里的LNode是类型别名，后面写LNode *p就行了，不用写struct LNode *p。但你在结构体内部声明指针时，不能用LNode *next，因为那一刻别名还没定义完，必须写struct LNode *next。这个细节我在刚学的时候纠结了很久，其实就是“你还没给人家起好小名，不能直接喊小名”。

C++里通常封装成类或者沿用结构体，配合指针new/delete。C++的引用传参给链表操作带来了一点舒适感，比如头插时传LNode *&head，可以省掉二级指针的繁琐写法。但要注意，C++的new和C的malloc混用时要小心释放方式，new出来的一定用delete，malloc出来的一定用free。混着用，某些编译器下不会立刻报错，但会埋下未定义行为的雷。

Python的链表实现则完全是另一套思路，没有指针语法，节点就是一个普通对象，next是对象引用，本质上也实现了“指向下一个节点”的效果。比如：

class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next

在Python里，“指针”这个概念被对象引用替代了，你不必担心野指针，垃圾回收机制会帮你处理不再被引用的节点。代价是，如果你用C那样的手写链表思路去实现Python链表，每个节点的属性访问都有额外开销，性能其实并不好看。刷LeetCode用Python写链表，图的是写法简洁、方便调试，不是真的要在Python里建一个高并发的链表服务。

6.2 Python单链表逆序与动态语言特性

拿“单链表逆序”这个经典操作举例，Python的迭代版几乎把C版照着翻译就行：

class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def reverse_list(head: ListNode) -> ListNode: pre = None cur = head while cur: nxt = cur.next cur.next = pre pre = cur cur = nxt return pre

这里有一个和C完全不同的地方：C里你操作的是裸指针，改指针时格外小心；Python里操作的是对象引用，改cur.next不会真的让变量cur失效。但逻辑顺序还是一样的，必须先暂存原来的nxt，再改cur.next。如果你直接写cur.next = pre，原来的下一个节点就找不到了，后面没法继续遍历。

Python还有一种很有Python味的解法：用元组交换。

def reverse_list(head: ListNode) -> ListNode: pre = None cur = head while cur: cur.next, pre, cur = pre, cur, cur.next return pre

注意cur.next和cur在一个元组里，右边先整体求值再赋值，所以cur.next, pre, cur = pre, cur, cur.next这行里，右边的cur.next取的是更新前的值，赋值后才分别生效。这样写很炫，但可读性差一点，自己写着玩可以，团队协作里我还是建议写三行版。

Python递归版同样简洁：

def reverse_list(head: ListNode) -> ListNode: if not head or not head.next: return head new_head = reverse_list(head.next) head.next.next = head head.next = None return new_head

这段跟C递归版的逻辑完全一致。你要是能在C和Python之间无障碍互译，说明你是真理解了链表的底层结构，而不只是背了几行代码。

7. 链表应用的实战心得：从实验课到工程代码

最后聊点我在实际写代码过程中沉淀下来的体会。链表这个数据结构，在大学课程里地位很高，几乎每本教材都拿它当重点，但你要是在业务系统里写业务逻辑，纯手写链表的机会确实不多。这造成了不少人的困惑：既然工程里不怎么用，为什么面试要考、实验要写？

我的理解是，链表训练的不是“链表本身”，而是对内存布局、指针引用、边界条件的敏感度。能写好链表的人，写普通业务代码时，对空值判断、生命周期、边界情况的把握都会明显更稳。所以别觉得链表没实际用，它更像底层程序员的基本功。

具体到操作层面，我有几条自己的经验：

第一，画图比写代码更管用。每次做链表插入删除前，先在纸上把节点和箭头画出来，标清楚操作顺序，再动手写。链表的操作本质上就是改箭头，画图能让你一眼看出哪里会丢链、哪里会产生环。尤其逆置，画一遍迭代过程的指针走向，比背十遍代码深刻得多。

第二，写单链表操作时，先写“空表情况”和“第一个节点情况”。这两种情况是问题高发区，如果你用不带头结点的链表，第一个节点插入删除都要特判，那一堆if就是最容易出bug的地方。改用带头结点的结构后，这两种情况都归并到普通逻辑里了。

第三，别迷信“链表的插入删除是O(1)”这句话。这句话说的是在你已经持有前驱节点指针的前提下。实际你通常只有值或者下标，得先花O(n)找到前驱，所以整体还是O(n)。面试时如果你把这一点说清楚，面试官往往会对你的理解程度高看一眼，我自己当面试官时听到这种回答也会加印象分。

第四，实验课检测题多练几个“应用型变体”。比如合并两条有序链表、判断回文链表、找链表中间节点、约瑟夫环问题。这些题目本质都是链表的遍历、插入、删除的组合拳。把基础操作练扎实，这些题看着花哨，拆开全是老朋友。

我记得刚接触链表那会儿，一个循环单链表的尾插法就让我折腾了半晚上，原因特别愚蠢——我忘了把最后节点的next指向头节点，结果一路NULL到底，程序遍历一遍停下来，毫无反应。后来我把所有链表题都当成“画箭头游戏”来玩，心态一下就好多了。

链表教会我的最重要的事，是任何数据结构都要先问清楚“为什么设计成这样”。单链表的弱点催生了双链表，双链表的空间浪费催生了各种变体，循环解决了“绕圈”的需求，带头结点解决了“边界”的繁琐。你顺着这条逻辑线走一遍，再看任何链表操作都不觉得玄了。以后写代码遇到需要频繁插入删除又不想复制大块数据的场景，你自然会想到链表；遇到需要大量随机访问的场景，你也自然会把它放下，去选数组。这比单纯记住“链表复杂度是O(1)”要有用得多。