直接说结论链表这玩意儿是C语言学习路上绕不过去的坎也是区分“会写C语法”和“懂C语言数据结构”的一道分水岭。很多人学完指针、结构体、动态内存分配觉得自己会了一到写链表就卡壳。头插尾插搞反、遍历条件写错、free之后没置NULL、内存泄漏查半天……这些都是学链表时的经典名场面。这篇文章就用最简单的版本把单向链表和单向循环链表从头到尾撸一遍代码可以直接抄每一步我都讲清楚为什么要这么写以及你在自己练习时最容易踩哪些坑。适合刚学完指针和结构体、准备啃数据结构的C语言新手也适合考试前想快速过一遍链表核心操作的兄弟。1. 先想清楚链表到底解决什么问题1.1 从数组到链表的必然性很多人第一门语言学的就是C接触的第一个数据结构就是数组。数组用起来确实简单int a[100]一个循环就能遍历下标访问还快。但数组的毛病也很明显长度写死了存满了就得换大数组数据少了又浪费空间往中间插入一个元素后面的全得往后挪删除也一样成本很高。链表就是冲着这两个痛点来的。它不要求元素在内存里连续存放每个节点都是独立malloc出来的用一个指针串起下一个节点。想插一个节点改两条指针就行不需要挪数据。想扩容再malloc一个节点挂上就是。代价是没法按下标直接访问想找第5个节点得从头往后走5步。这个“空间换时间、灵活换随机访问”的取舍是整个数据结构的核心思想。1.2 单向链表和单向循环链表的关系单向链表是最基础的形态每个节点只有一个next指针指向后继节点最后一个节点的next指向NULL表示“到头了”。单向循环链表就是在此基础上做了一个小修改让最后一个节点的next不再指向NULL而是指回头节点。这样一来整条链表形成一个环从任意节点出发都能走回自己。很多初学者会觉得循环链表没什么用其实你想想操作系统里的进程调度轮转、游戏里玩家轮流操作、数据缓冲区循环覆盖读写这些都是环形结构的典型场景。C语言课程里最经典的练习题目——约瑟夫环问题用的就是单向循环链表。1.3 前置知识指针、结构体、动态内存写链表之前有三个前置技能点必须过关结构体定义用struct把“数据域 指针域”打包成一个节点类型。指针操作理解p-next到底取的是什么以及二级指针什么时候用得上。malloc和free节点是动态分配的谁malloc的谁负责free这个规矩从学链表第一天就要刻在脑子里。如果你这三点还有点虚建议先写几个小例子练练手再回来看这篇文章。2. 单向链表从零开始写一个能跑的版本2.1 结构体定义节点长什么样先定义一个节点结构体为了简单起见数据域放一个inttypedef struct Node { int data; /* 数据域 */ struct Node *next; /* 指针域指向下一个节点 */ } Node;注意这里用的是struct Node *next不是Node *next因为typedef还没生效结构体内部只能用自己的完整名字。这是个很容易被忽视的小细节自己定义链表节点时经常会在这里报编译错误。2.2 创建节点malloc不是随便用的任何链表操作的第一步都是创建节点。创建节点时最容易犯的错误就是忘了判断malloc的返回值。内存分配失败返回NULL你不做检查直接使用程序崩溃只是时间问题。Node *createNode(int val) { Node *newNode (Node *)malloc(sizeof(Node)); if (newNode NULL) { printf(内存分配失败\n); exit(1); } newNode-data val; newNode-next NULL; return newNode; }2.3 头插法代码最简洁的插入方式头插法的核心思想新节点插在链表头部成为新的头节点。头插法代码非常短但容易在指针顺序上犯迷糊。Node *insertAtHead(Node *head, int val) { Node *newNode createNode(val); newNode-next head; /* 先让新节点指向原头节点 */ head newNode; /* 再更新头指针 */ return head; }关键点在于newNode-next head这一步必须在head newNode之前完成。如果你先让head等于newNode头指针就指向新节点了原来的链表就找不到了这叫“断链”是链表操作里最经典的事故现场。2.4 尾插法需要遍历找到最后一个节点尾插法要在链表末尾追加节点需要先走到最后一个节点。最后一个节点的特征是p-next NULL。Node *insertAtTail(Node *head, int val) { Node *newNode createNode(val); if (head NULL) { head newNode; return head; } Node *p head; while (p-next ! NULL) { p p-next; } p-next newNode; return head; }这里有个边界条件必须考虑如果链表为空头插和尾插都是直接让头指针指向新节点。很多初学者写尾插时不写head NULL的判断导致空链表直接段错误这是第一个容易踩的坑。2.5 遍历打印迭代法就够用遍历的思路很简单从头开始每访问一个节点打印数据然后p移动到下一个节点直到p为NULL。void printList(Node *head) { Node *p head; while (p ! NULL) { printf(%d - , p-data); p p-next; } printf(NULL\n); }2.6 删除节点必须记住前驱节点删除节点分三种情况删除头节点、删除中间节点、删除末尾节点。核心思路是找到“待删除节点的前一个节点”让前一个节点的next跳过待删除节点直指后继节点最后free掉待删除节点。Node *deleteNode(Node *head, int target) { Node *p head; Node *prev NULL; /* 头节点就是目标 */ if (p ! NULL p-data target) { head p-next; free(p); return head; } /* 查找目标节点同时记录前驱 */ while (p ! NULL p-data ! target) { prev p; p p-next; } if (p NULL) { printf(没找到目标节点\n); return head; } prev-next p-next; free(p); return head; }说一句题外话删除节点时用prev记录前驱这个技巧在双向链表、二叉树删除、LRU缓存等很多场景都会用到。它不是冷门技巧而是链表算法的通用基本功值得多写几遍形成肌肉记忆。2.7 销毁链表释放每个节点的内存写链表时大家最容易忽略的操作就是销毁链表。程序结束前要把所有malloc出来的节点都free掉否则就是内存泄漏。void freeList(Node *head) { Node *p head; while (p ! NULL) { Node *tmp p; p p-next; free(tmp); } }这里有两点要注意第一free之前必须先把下一个节点的地址保存下来第二你如果把这个函数用在循环链表上while (p ! NULL)会死循环因为循环链表里next永远不会为NULL——这一点等会儿讲到循环链表的时候再具体说。2.8 一个完整的单向链表功能演示把上面的函数拼在一起写一个简单的菜单程序方便你对照着编译测一下#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; Node *createNode(int val) { Node *newNode (Node *)malloc(sizeof(Node)); if (newNode NULL) { printf(内存分配失败\n); exit(1); } newNode-data val; newNode-next NULL; return newNode; } Node *insertAtHead(Node *head, int val) { Node *newNode createNode(val); newNode-next head; head newNode; return head; } Node *insertAtTail(Node *head, int val) { Node *newNode createNode(val); if (head NULL) { head newNode; return head; } Node *p head; while (p-next ! NULL) { p p-next; } p-next newNode; return head; } void printList(Node *head) { Node *p head; while (p ! NULL) { printf(%d - , p-data); p p-next; } printf(NULL\n); } Node *deleteNode(Node *head, int target) { Node *p head; Node *prev NULL; if (p ! NULL p-data target) { head p-next; free(p); return head; } while (p ! NULL p-data ! target) { prev p; p p-next; } if (p NULL) { printf(没找到目标节点\n); return head; } prev-next p-next; free(p); return head; } void freeList(Node *head) { Node *p head; while (p ! NULL) { Node *tmp p; p p-next; free(tmp); } } int main(void) { Node *head NULL; head insertAtTail(head, 10); head insertAtTail(head, 20); head insertAtTail(head, 30); head insertAtHead(head, 5); printList(head); head deleteNode(head, 20); printList(head); freeList(head); return 0; }编译运行一下gcc -Wall -o demo demo.c ./demo输出结果为5 - 10 - 20 - 30 - NULL 5 - 10 - 30 - NULL注意编译时别忘了加-Wall选项让编译器把警告都打出来。写链表代码遇到编译警告一定要重视很多警告背后就是野指针或类型不匹配的隐患。3. 单向循环链表只改一处next的指向3.1 循环链表和单向链表的核心区别单向循环链表和普通单向链表结构体定义其实是一样的就一个区别普通单向链表最后一个节点的next指向NULL循环链表的最后一个节点next指向头节点。操作上的差异主要体现在两点遍历的终止条件从p-next ! NULL变成了p-next ! head或者用计数器控制循环次数删除、查找时对空链表和单节点链表的判断要更小心。3.2 约瑟夫环循环链表最经典的场景约瑟夫环这个问题我第一次在翁恺老师的C语言练习题里看到的时候就印象深刻。问题大意是N个人围成一圈从第1个人开始报数报到M的人出列然后从下一个人开始重新报数如此循环直到所有人出列求最后剩下的那个人或者输出完整的出列顺序。围成一圈、循环报数、淘汰出列——这不就是循环链表最自然的应用场景吗每个人是链表里的一个节点报数就是沿链表走下去报到M就删除当前节点然后继续。3.3 约瑟夫环的C语言实现下面这个实现我尽量写得贴近真实项目习惯创建一个规模为N的循环链表模拟报数M出列的过程打印出列顺序最后打印幸存者。#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; Node *createNode(int val) { Node *newNode (Node *)malloc(sizeof(Node)); if (newNode NULL) { printf(内存分配失败\n); exit(1); } newNode-data val; newNode-next NULL; return newNode; } /* 创建包含n个节点的循环链表数据为1到n */ Node *createCircularList(int n) { Node *head NULL; Node *tail NULL; for (int i 1; i n; i) { Node *newNode createNode(i); if (head NULL) { head newNode; tail newNode; } else { tail-next newNode; tail newNode; } } tail-next head; /* 关键让末尾节点指向头节点形成环 */ return head; } void josephus(Node *head, int m) { Node *p head; Node *prev NULL; /* 先让prev指向p的前驱。 对循环链表来说从头节点出发走一圈能回到头节点 所以最自然的做法是先让prev走到p的前一个节点。 */ prev p; while (prev-next ! p) { prev prev-next; } printf(出列顺序); while (p-next ! p) { /* 只要环里还有多于1个节点 */ /* 报数1到m-1走到要删除的节点 */ for (int i 1; i m; i) { prev p; p p-next; } printf(%d , p-data); /* 删除当前节点 */ prev-next p-next; free(p); p prev-next; /* 从被删节点的下一个节点继续报数 */ } printf(\n最后剩下%d\n, p-data); free(p); } int main(void) { /* 例如5个人报到3出列 */ Node *head createCircularList(5); josephus(head, 3); return 0; }运行结果出列顺序3 1 5 2 最后剩下4你可以自己拿纸笔画一画验证一下看看这个结果对不对。这个模拟过程建议亲手走一遍比看十遍代码都管用。3.4 循环链表的遍历和销毁要注意什么循环链表的遍历不能再用while (p ! NULL)了因为环里永远不会出现NULL。常见做法是从头节点开始用do-while先执行一次再判断是否回到头节点或者遍历到p-next head时停止。销毁循环链表也要特别处理先保存头节点然后从头节点开始遍历当p-next ! head时不断free当前节点循环结束再free头节点。如果你图省事用单向链表的销毁函数去处理循环链表结果就是一个死循环程序卡死这也是很多初学者踩过的坑。3.5 循环链表的一个实用改造尾指针刚才创建循环链表的时候其实需要保留tail尾节点来快速接入新节点。稍微优化一下可以不在链表里存储头指针而是存储尾指针——也就是让tail-next指向head。为什么要这么做因为有了尾指针在末尾插入一个节点就变成了O(1)操作不用再从头遍历到末尾。而通过tail-next就能快速拿到头节点。这是循环链表在实际工程里非常常见的一个改造方向面试时如果你能主动提到这一点印象分会好很多。4. 常见问题与排查技巧实录4.1 野指针free之后不置NULL的后果我在带新人写代码时见过太多类似的段错误。典型例子是删除节点时delete函数里free(p)了但main函数的某个指针还保存着被删节点的地址继续用这个指针去访问数据程序不出问题才怪。我自己的习惯是每次free一个指针之后立刻把它置为NULL。虽然C语言里没有“强制必须置NULL”的规则但不置NULL的话这个指针就成了野指针。你留着它以后可能引发“悬空指针”问题排查起来非常痛苦。4.2 断链修改指针顺序的黄金法则链表操作的一切错误归结到最后都是“指针连错了”。有一个黄金法则可以少踩无数坑先接新的再拆旧的。以头插法为例先让新节点的next指向原来的头节点再把head更新为新节点。如果你先改head就相当于把原来的链表给丢了后面的节点找不回来了——这就是“断链”。凡是涉及插入、删除的操作写代码前先在心里把指针的先后顺序过一遍养成这个习惯之后链表相关的bug至少能减少一半。4.3 空链表与单节点边界条件最容易漏链表里最简单也最容易被忽略的两个边界情况就是空链表和只有一个节点的链表。空链表做任何操作之前都要先判断head ! NULL。很多初学者在写删除函数的时候上来就判断head-data是否等于目标值如果head是NULL这一步直接段错误。单节点链表在删除时也有坑。如果你删的是唯一的那个节点删除之后head应该变成NULL而不是继续指向那个已被free的内存。循环链表里单节点更是特殊——比如刚才约瑟夫环的while (p-next ! p)循环小于等于1个人时整个循环体根本不会进去逻辑就要额外处理。建议你在写完链表函数后专门用“空链表、单节点链表、双节点链表”三组数据各测一遍这三个边界能过说明函数基本是稳的。4.4 内存泄漏用工具帮你查C语言没有自动垃圾回收全靠自觉。写链表程序最直接的检查方式是valgrindvalgrind --leak-checkfull ./demo如果输出中出现了“definitely lost”说明你有malloc没有对应的free。这种问题堆得多了程序长期跑下来内存会有明显增长这在嵌入式环境下是非常致命的。如果没有条件用valgrind也可以自己在程序里加统计信息比如每次createNode时全局计数1每次free时全局计数-1最后打印计数是否为0。这种“土办法”在面试现场反而是加分项能体现出你对内存管理的理解。4.5 调试笨办法画图比加日志快看指针代码很多人第一反应是加printf输出日志。我的经验是链表这种几步一个指针变更的逻辑打印一屏日志远不如拿张纸画个链表图来得快。把每个节点的data、next箭头都画下来然后一步步执行你的代码用笔把箭头改过来。循环几次之后你会发现很多bug其实在你动笔之前就已经能预判到了。这个方法听起来土但真的比瞪眼干看代码高效太多。5. 写出高质量的链表代码5.1 防御性编程输入参数先判空一个合格的函数第一步应该是检查传入参数是否合法。比如遍历打印函数如果head为NULL直接返回。删除函数如果head为NULL或者目标值不存在也要有相应的处理逻辑不能默默崩溃或输出错误结果。这些判断看似多余但在实际项目中链表往往在很复杂的业务流程里被反复调用输入不可控是常态。你不写防御性判断当场可能没问题一旦数据异常段错误直接甩给你连个错误提示都没有。5.2 函数拆分一个函数只干一件事观察我上面写的代码你会发现每个函数都很短createNode只负责创建节点insertAtHead只负责头插printList只负责遍历。这就是函数拆分的意义所在。很多初学者喜欢把创建、遍历、删除全塞进一个main函数里几百行代码连成一片。这种代码自己调试都费劲更别说别人看了。分段拆细之后每个函数都能单独验证定位问题也快得多。5.3 面试和考试里高频考法链表是各大笔试面试的基础题题型我列几个常见的反转一个单向链表判断链表中是否有环快慢指针法合并两个有序链表找链表的中间节点快慢指针法约瑟夫环问题循环链表链表排序这些题目我在面试中见过不少基本功都在于你今天对单向链表和循环链表的理解。有的同学背题能背下来稍微变一下条件就懵本质原因还是对指针操作没形成直觉。结尾说实话链表这套东西光看文章是不够的。我自己的体会是把上面这几十行代码照着敲一遍再自己动手画一遍指针指向图最后用valgrind查一遍内存泄漏这一套流程走完你对指针和动态内存的理解会上一个台阶。建议你写完这个简单版之后再去试试反转链表、快慢指针找环这些进阶题目你会发现它们其实都是基于“先接新的再拆旧的”“记住前驱节点”“边界条件先判断”这几个最朴素的规律。写链表出错不可怕可怕的是一直不自己动手写。 C语言链表入门：单向链表与循环链表核心操作详解
直接说结论链表这玩意儿是C语言学习路上绕不过去的坎也是区分“会写C语法”和“懂C语言数据结构”的一道分水岭。很多人学完指针、结构体、动态内存分配觉得自己会了一到写链表就卡壳。头插尾插搞反、遍历条件写错、free之后没置NULL、内存泄漏查半天……这些都是学链表时的经典名场面。这篇文章就用最简单的版本把单向链表和单向循环链表从头到尾撸一遍代码可以直接抄每一步我都讲清楚为什么要这么写以及你在自己练习时最容易踩哪些坑。适合刚学完指针和结构体、准备啃数据结构的C语言新手也适合考试前想快速过一遍链表核心操作的兄弟。1. 先想清楚链表到底解决什么问题1.1 从数组到链表的必然性很多人第一门语言学的就是C接触的第一个数据结构就是数组。数组用起来确实简单int a[100]一个循环就能遍历下标访问还快。但数组的毛病也很明显长度写死了存满了就得换大数组数据少了又浪费空间往中间插入一个元素后面的全得往后挪删除也一样成本很高。链表就是冲着这两个痛点来的。它不要求元素在内存里连续存放每个节点都是独立malloc出来的用一个指针串起下一个节点。想插一个节点改两条指针就行不需要挪数据。想扩容再malloc一个节点挂上就是。代价是没法按下标直接访问想找第5个节点得从头往后走5步。这个“空间换时间、灵活换随机访问”的取舍是整个数据结构的核心思想。1.2 单向链表和单向循环链表的关系单向链表是最基础的形态每个节点只有一个next指针指向后继节点最后一个节点的next指向NULL表示“到头了”。单向循环链表就是在此基础上做了一个小修改让最后一个节点的next不再指向NULL而是指回头节点。这样一来整条链表形成一个环从任意节点出发都能走回自己。很多初学者会觉得循环链表没什么用其实你想想操作系统里的进程调度轮转、游戏里玩家轮流操作、数据缓冲区循环覆盖读写这些都是环形结构的典型场景。C语言课程里最经典的练习题目——约瑟夫环问题用的就是单向循环链表。1.3 前置知识指针、结构体、动态内存写链表之前有三个前置技能点必须过关结构体定义用struct把“数据域 指针域”打包成一个节点类型。指针操作理解p-next到底取的是什么以及二级指针什么时候用得上。malloc和free节点是动态分配的谁malloc的谁负责free这个规矩从学链表第一天就要刻在脑子里。如果你这三点还有点虚建议先写几个小例子练练手再回来看这篇文章。2. 单向链表从零开始写一个能跑的版本2.1 结构体定义节点长什么样先定义一个节点结构体为了简单起见数据域放一个inttypedef struct Node { int data; /* 数据域 */ struct Node *next; /* 指针域指向下一个节点 */ } Node;注意这里用的是struct Node *next不是Node *next因为typedef还没生效结构体内部只能用自己的完整名字。这是个很容易被忽视的小细节自己定义链表节点时经常会在这里报编译错误。2.2 创建节点malloc不是随便用的任何链表操作的第一步都是创建节点。创建节点时最容易犯的错误就是忘了判断malloc的返回值。内存分配失败返回NULL你不做检查直接使用程序崩溃只是时间问题。Node *createNode(int val) { Node *newNode (Node *)malloc(sizeof(Node)); if (newNode NULL) { printf(内存分配失败\n); exit(1); } newNode-data val; newNode-next NULL; return newNode; }2.3 头插法代码最简洁的插入方式头插法的核心思想新节点插在链表头部成为新的头节点。头插法代码非常短但容易在指针顺序上犯迷糊。Node *insertAtHead(Node *head, int val) { Node *newNode createNode(val); newNode-next head; /* 先让新节点指向原头节点 */ head newNode; /* 再更新头指针 */ return head; }关键点在于newNode-next head这一步必须在head newNode之前完成。如果你先让head等于newNode头指针就指向新节点了原来的链表就找不到了这叫“断链”是链表操作里最经典的事故现场。2.4 尾插法需要遍历找到最后一个节点尾插法要在链表末尾追加节点需要先走到最后一个节点。最后一个节点的特征是p-next NULL。Node *insertAtTail(Node *head, int val) { Node *newNode createNode(val); if (head NULL) { head newNode; return head; } Node *p head; while (p-next ! NULL) { p p-next; } p-next newNode; return head; }这里有个边界条件必须考虑如果链表为空头插和尾插都是直接让头指针指向新节点。很多初学者写尾插时不写head NULL的判断导致空链表直接段错误这是第一个容易踩的坑。2.5 遍历打印迭代法就够用遍历的思路很简单从头开始每访问一个节点打印数据然后p移动到下一个节点直到p为NULL。void printList(Node *head) { Node *p head; while (p ! NULL) { printf(%d - , p-data); p p-next; } printf(NULL\n); }2.6 删除节点必须记住前驱节点删除节点分三种情况删除头节点、删除中间节点、删除末尾节点。核心思路是找到“待删除节点的前一个节点”让前一个节点的next跳过待删除节点直指后继节点最后free掉待删除节点。Node *deleteNode(Node *head, int target) { Node *p head; Node *prev NULL; /* 头节点就是目标 */ if (p ! NULL p-data target) { head p-next; free(p); return head; } /* 查找目标节点同时记录前驱 */ while (p ! NULL p-data ! target) { prev p; p p-next; } if (p NULL) { printf(没找到目标节点\n); return head; } prev-next p-next; free(p); return head; }说一句题外话删除节点时用prev记录前驱这个技巧在双向链表、二叉树删除、LRU缓存等很多场景都会用到。它不是冷门技巧而是链表算法的通用基本功值得多写几遍形成肌肉记忆。2.7 销毁链表释放每个节点的内存写链表时大家最容易忽略的操作就是销毁链表。程序结束前要把所有malloc出来的节点都free掉否则就是内存泄漏。void freeList(Node *head) { Node *p head; while (p ! NULL) { Node *tmp p; p p-next; free(tmp); } }这里有两点要注意第一free之前必须先把下一个节点的地址保存下来第二你如果把这个函数用在循环链表上while (p ! NULL)会死循环因为循环链表里next永远不会为NULL——这一点等会儿讲到循环链表的时候再具体说。2.8 一个完整的单向链表功能演示把上面的函数拼在一起写一个简单的菜单程序方便你对照着编译测一下#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; Node *createNode(int val) { Node *newNode (Node *)malloc(sizeof(Node)); if (newNode NULL) { printf(内存分配失败\n); exit(1); } newNode-data val; newNode-next NULL; return newNode; } Node *insertAtHead(Node *head, int val) { Node *newNode createNode(val); newNode-next head; head newNode; return head; } Node *insertAtTail(Node *head, int val) { Node *newNode createNode(val); if (head NULL) { head newNode; return head; } Node *p head; while (p-next ! NULL) { p p-next; } p-next newNode; return head; } void printList(Node *head) { Node *p head; while (p ! NULL) { printf(%d - , p-data); p p-next; } printf(NULL\n); } Node *deleteNode(Node *head, int target) { Node *p head; Node *prev NULL; if (p ! NULL p-data target) { head p-next; free(p); return head; } while (p ! NULL p-data ! target) { prev p; p p-next; } if (p NULL) { printf(没找到目标节点\n); return head; } prev-next p-next; free(p); return head; } void freeList(Node *head) { Node *p head; while (p ! NULL) { Node *tmp p; p p-next; free(tmp); } } int main(void) { Node *head NULL; head insertAtTail(head, 10); head insertAtTail(head, 20); head insertAtTail(head, 30); head insertAtHead(head, 5); printList(head); head deleteNode(head, 20); printList(head); freeList(head); return 0; }编译运行一下gcc -Wall -o demo demo.c ./demo输出结果为5 - 10 - 20 - 30 - NULL 5 - 10 - 30 - NULL注意编译时别忘了加-Wall选项让编译器把警告都打出来。写链表代码遇到编译警告一定要重视很多警告背后就是野指针或类型不匹配的隐患。3. 单向循环链表只改一处next的指向3.1 循环链表和单向链表的核心区别单向循环链表和普通单向链表结构体定义其实是一样的就一个区别普通单向链表最后一个节点的next指向NULL循环链表的最后一个节点next指向头节点。操作上的差异主要体现在两点遍历的终止条件从p-next ! NULL变成了p-next ! head或者用计数器控制循环次数删除、查找时对空链表和单节点链表的判断要更小心。3.2 约瑟夫环循环链表最经典的场景约瑟夫环这个问题我第一次在翁恺老师的C语言练习题里看到的时候就印象深刻。问题大意是N个人围成一圈从第1个人开始报数报到M的人出列然后从下一个人开始重新报数如此循环直到所有人出列求最后剩下的那个人或者输出完整的出列顺序。围成一圈、循环报数、淘汰出列——这不就是循环链表最自然的应用场景吗每个人是链表里的一个节点报数就是沿链表走下去报到M就删除当前节点然后继续。3.3 约瑟夫环的C语言实现下面这个实现我尽量写得贴近真实项目习惯创建一个规模为N的循环链表模拟报数M出列的过程打印出列顺序最后打印幸存者。#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; Node *createNode(int val) { Node *newNode (Node *)malloc(sizeof(Node)); if (newNode NULL) { printf(内存分配失败\n); exit(1); } newNode-data val; newNode-next NULL; return newNode; } /* 创建包含n个节点的循环链表数据为1到n */ Node *createCircularList(int n) { Node *head NULL; Node *tail NULL; for (int i 1; i n; i) { Node *newNode createNode(i); if (head NULL) { head newNode; tail newNode; } else { tail-next newNode; tail newNode; } } tail-next head; /* 关键让末尾节点指向头节点形成环 */ return head; } void josephus(Node *head, int m) { Node *p head; Node *prev NULL; /* 先让prev指向p的前驱。 对循环链表来说从头节点出发走一圈能回到头节点 所以最自然的做法是先让prev走到p的前一个节点。 */ prev p; while (prev-next ! p) { prev prev-next; } printf(出列顺序); while (p-next ! p) { /* 只要环里还有多于1个节点 */ /* 报数1到m-1走到要删除的节点 */ for (int i 1; i m; i) { prev p; p p-next; } printf(%d , p-data); /* 删除当前节点 */ prev-next p-next; free(p); p prev-next; /* 从被删节点的下一个节点继续报数 */ } printf(\n最后剩下%d\n, p-data); free(p); } int main(void) { /* 例如5个人报到3出列 */ Node *head createCircularList(5); josephus(head, 3); return 0; }运行结果出列顺序3 1 5 2 最后剩下4你可以自己拿纸笔画一画验证一下看看这个结果对不对。这个模拟过程建议亲手走一遍比看十遍代码都管用。3.4 循环链表的遍历和销毁要注意什么循环链表的遍历不能再用while (p ! NULL)了因为环里永远不会出现NULL。常见做法是从头节点开始用do-while先执行一次再判断是否回到头节点或者遍历到p-next head时停止。销毁循环链表也要特别处理先保存头节点然后从头节点开始遍历当p-next ! head时不断free当前节点循环结束再free头节点。如果你图省事用单向链表的销毁函数去处理循环链表结果就是一个死循环程序卡死这也是很多初学者踩过的坑。3.5 循环链表的一个实用改造尾指针刚才创建循环链表的时候其实需要保留tail尾节点来快速接入新节点。稍微优化一下可以不在链表里存储头指针而是存储尾指针——也就是让tail-next指向head。为什么要这么做因为有了尾指针在末尾插入一个节点就变成了O(1)操作不用再从头遍历到末尾。而通过tail-next就能快速拿到头节点。这是循环链表在实际工程里非常常见的一个改造方向面试时如果你能主动提到这一点印象分会好很多。4. 常见问题与排查技巧实录4.1 野指针free之后不置NULL的后果我在带新人写代码时见过太多类似的段错误。典型例子是删除节点时delete函数里free(p)了但main函数的某个指针还保存着被删节点的地址继续用这个指针去访问数据程序不出问题才怪。我自己的习惯是每次free一个指针之后立刻把它置为NULL。虽然C语言里没有“强制必须置NULL”的规则但不置NULL的话这个指针就成了野指针。你留着它以后可能引发“悬空指针”问题排查起来非常痛苦。4.2 断链修改指针顺序的黄金法则链表操作的一切错误归结到最后都是“指针连错了”。有一个黄金法则可以少踩无数坑先接新的再拆旧的。以头插法为例先让新节点的next指向原来的头节点再把head更新为新节点。如果你先改head就相当于把原来的链表给丢了后面的节点找不回来了——这就是“断链”。凡是涉及插入、删除的操作写代码前先在心里把指针的先后顺序过一遍养成这个习惯之后链表相关的bug至少能减少一半。4.3 空链表与单节点边界条件最容易漏链表里最简单也最容易被忽略的两个边界情况就是空链表和只有一个节点的链表。空链表做任何操作之前都要先判断head ! NULL。很多初学者在写删除函数的时候上来就判断head-data是否等于目标值如果head是NULL这一步直接段错误。单节点链表在删除时也有坑。如果你删的是唯一的那个节点删除之后head应该变成NULL而不是继续指向那个已被free的内存。循环链表里单节点更是特殊——比如刚才约瑟夫环的while (p-next ! p)循环小于等于1个人时整个循环体根本不会进去逻辑就要额外处理。建议你在写完链表函数后专门用“空链表、单节点链表、双节点链表”三组数据各测一遍这三个边界能过说明函数基本是稳的。4.4 内存泄漏用工具帮你查C语言没有自动垃圾回收全靠自觉。写链表程序最直接的检查方式是valgrindvalgrind --leak-checkfull ./demo如果输出中出现了“definitely lost”说明你有malloc没有对应的free。这种问题堆得多了程序长期跑下来内存会有明显增长这在嵌入式环境下是非常致命的。如果没有条件用valgrind也可以自己在程序里加统计信息比如每次createNode时全局计数1每次free时全局计数-1最后打印计数是否为0。这种“土办法”在面试现场反而是加分项能体现出你对内存管理的理解。4.5 调试笨办法画图比加日志快看指针代码很多人第一反应是加printf输出日志。我的经验是链表这种几步一个指针变更的逻辑打印一屏日志远不如拿张纸画个链表图来得快。把每个节点的data、next箭头都画下来然后一步步执行你的代码用笔把箭头改过来。循环几次之后你会发现很多bug其实在你动笔之前就已经能预判到了。这个方法听起来土但真的比瞪眼干看代码高效太多。5. 写出高质量的链表代码5.1 防御性编程输入参数先判空一个合格的函数第一步应该是检查传入参数是否合法。比如遍历打印函数如果head为NULL直接返回。删除函数如果head为NULL或者目标值不存在也要有相应的处理逻辑不能默默崩溃或输出错误结果。这些判断看似多余但在实际项目中链表往往在很复杂的业务流程里被反复调用输入不可控是常态。你不写防御性判断当场可能没问题一旦数据异常段错误直接甩给你连个错误提示都没有。5.2 函数拆分一个函数只干一件事观察我上面写的代码你会发现每个函数都很短createNode只负责创建节点insertAtHead只负责头插printList只负责遍历。这就是函数拆分的意义所在。很多初学者喜欢把创建、遍历、删除全塞进一个main函数里几百行代码连成一片。这种代码自己调试都费劲更别说别人看了。分段拆细之后每个函数都能单独验证定位问题也快得多。5.3 面试和考试里高频考法链表是各大笔试面试的基础题题型我列几个常见的反转一个单向链表判断链表中是否有环快慢指针法合并两个有序链表找链表的中间节点快慢指针法约瑟夫环问题循环链表链表排序这些题目我在面试中见过不少基本功都在于你今天对单向链表和循环链表的理解。有的同学背题能背下来稍微变一下条件就懵本质原因还是对指针操作没形成直觉。结尾说实话链表这套东西光看文章是不够的。我自己的体会是把上面这几十行代码照着敲一遍再自己动手画一遍指针指向图最后用valgrind查一遍内存泄漏这一套流程走完你对指针和动态内存的理解会上一个台阶。建议你写完这个简单版之后再去试试反转链表、快慢指针找环这些进阶题目你会发现它们其实都是基于“先接新的再拆旧的”“记住前驱节点”“边界条件先判断”这几个最朴素的规律。写链表出错不可怕可怕的是一直不自己动手写。