C算法
链表基础与实战：单双链表实现及经典算法题解析
详细讲解了链表的数据结构概念、分类及手动实现方法。内容包括单链表的初始化、增删改查操作，以及二级指针的使用原理。通过对比顺序表分析链表优势，并结合 LeetCode 经典题目（如移除元素、反转链表、快慢指针等）进行实战演练。最后提供了单链表和双向带头循环链表的完整 C 语言源码，帮助读者深入理解内存管理与指针操作。
详细讲解了链表的数据结构概念、分类及手动实现方法。内容包括单链表的初始化、增删改查操作，以及二级指针的使用原理。通过对比顺序表分析链表优势，并结合 LeetCode 经典题目（如移除元素、反转链表、快慢指针等）进行实战演练。最后提供了单链表和双向带头循环链表的完整 C 语言源码，帮助读者深入理解内存管理与指针操作。
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
上述是书本的定义，链表也是属于线性表，所以在逻辑结构上是线性的，而由于链表的数据与数据之间是通过地址（指针）连接的，所以地址不一定连续，具体要看操作系统分配的地址是否连续。
下图是链表的形象表示：火车是通过一节一节车厢连接在一起，删除和增加某节车厢不影响其他车厢，即每个车厢都是独立存在，每节车厢是通过钩子连接起来这与链表中每个节点相互独立，却又通过该节点指向下一个节点的指针连接起来有异曲同工之处。
链表是由一个一个节点组成，节点由要存储的数据 + 下一个节点地址的指针。如图在第一个节点中保存的数据是 1，还有下一个节点的地址：0x0012FFB0，也就是第二个节点的地址。依次往后看，直到第四个节点保存的数据是 4，由于它的后面没有节点了，所以它保存的下一个节点的地址是 NULL。
链表的结构非常多，以下情况组合起来共有 8 种（2x2x2）链表结构：
在双向链表中，存放了两个指针：next 指向下一个节点（后继节点），prev 指向前一个节点（前驱节点）。
注意：在上课或者参考书上为了方便理解单链表会把链表的首节点称为头结点，但是这样的称呼是错误的，因为链表中存在一类链表叫做带头链表（不是指链表里的第一个有效的节点），这里的头结点即哨兵位（不保存任何有效数据，仅用来占位置，作用是不需要判断链表的头是否为空），如带头链表中只有头结点，那么我们就称该节点为空链表。
在循环链表中尾节点的指向不为空，它指向了链表中第一个有效的节点。
因此在前面我们实现的单链表的全称为：不带头单向不循环链表。链表有上面 8 种结构，但我们实际中用的最多的是单链表和双向带头循环链表！
节点里存储两个变量，这里数据存储使用 typedef 将全部 int 改名成 SLTDataType，方便以后修改，由于保存的下一个节点的地址也是节点类型，所以使用 SListNode* 类型，最后也把 struct SListNode 改名成 SLTNode，方便书写。
//定义节点的结构
typedef int SLTDataType;
typedef struct SListNode {
SLTDataType data;
struct SListNode* next;
} SLTNode;
在实现链表的打印功能前需要手动构造一个链表，如下：
SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode)); node1->data = 1;
SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode)); node2->data = 2;
SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode)); node3->data = 3;
SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode)); node4->data = 4;
node1->next = node2; node2->next = node3; node3->next = node4; node4->next =NULL;
以下是链表的打印，具体实现如下：
注意： 在这里直接使用 phead 来遍历也是一样的，重新创建 pcur 指针是为了避免由于指针指向的改变，导致无法重新找到链表的首节点。
void SLTPrint(SLTNode* phead){
//pcur 存放的是当前节点的地址
SLTNode* pcur = phead;
while(pcur){
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}
注意：这里要判断申请空间是否成功，如果失败退出，申请成功对 data 和 next 进行初始化。
SLTNode* SLTBuyNode(SLTDataType x){
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if(newnode ==NULL){
perror("malloc fail!\n");
exit(1);
}
newnode->data = x;
newnode->next =NULL;
return newnode;
}
向操作系统动态申请一个节点大小的空间 然后断言若传来的是 NULL，那么不能解引用，所以需要断言 pphead 不能为空，但是 *pphead 可以为空，因为它代表的是空链表，所以可以存在。这里尾插分两种情况。
链表为空：即 pphead 为空，则让 pphead 等于 newnode(为首节点) 即 1。
链表不为空：即 pphead 不为空，具体步骤如下：
这里我们发现形参 phead 的改变没有影响到实参 plist 的改变（在传值的时候，形参的改变不影响实参 传地址：形参的改变影响实参），所以 plist 应该传地址而不是值，应为&plist，而 plist 是指针，所以 phead 要传二级指针来接受一级指针的地址，所以为 **pphead。在 if 语句中药对 pphead 解引用（*pphead=plist）为一级指针，后面也是同样的意思。
这里解释下一级指针和二级指针的概念 第一个节点 （解引用） *plist<---------->**phead(解引用两次)，左边例如 plist 是实参，右边是形参 指向第一个节点的指针 plist<-------->*phead（解引用一次后变成一级指针） 指向第一个节点的指针的地址 （取地址） &plist<---------->pphead（二级指针）
//尾插
void SLTPushBack(SLTNode**pphead, SLTDataType x){
//如果传来的是 NULL，那么不能解引用，所以需要断言 pphead 不能为空，但是*pphead 可以为空，因为它代表的是空链表，所以可以存在
assert(pphead);
//*pphead 就是指向第一个节点的指针
//空链表和非空链表两种情况
SLTNode* newnode = SLTBuyNode(x);
if(*pphead ==NULL){
*pphead = newnode;
}else{
SLTNode* ptail =*pphead;
//如果 ptail 为空，那么在循环里面不可以对空指针解引用，所以会报错
while(ptail->next){
ptail = ptail->next;
}
//ptail 指向的就是尾节点
ptail->next = newnode;
}
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x){
//空链表和非空链表都可以运行
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
newnode->next =*pphead;
*pphead = newnode;
}
代码思路如下：
注意 这里断言时：pphead（一级指针的地址）不能为空，否则不能对二级指针解引用，其次不能让链表为空，总不能删空吧，这不可能的，所以和头插尾插不同的是添加了个（*pphead）不能为空。
//尾删
void SLTPopBack(SLTNode** pphead ){
//这里和头插尾差不一样，因为尾删的话，链表不能为空，总不能删空吧，这不可能的，所以和头插尾插不同的是添加了个*pphead 不能为空
assert(pphead &&*pphead);
//链表只有一个节点
if((*pphead)->next ==NULL)//这里给*pphead 加了个括号，因为有符号的优先级，->的优先级高于*号
{
free(*pphead);
*pphead =NULL;
}else{
//链表有多个节点
SLTNode* prev =*pphead;
SLTNode* ptail =*pphead;
while(ptail->next){
prev = ptail;
ptail = ptail->next;
}
free(ptail);
ptail =NULL;
prev->next =NULL;
}
}
注意：这里不能直接删除 pphead，若删除找不到后面的节点 2，所以需要定义 next 保存下一个节点 2。
//头删
void SLTPopFront(SLTNode** pphead){
//这里和尾删是一样的，解释在上面
assert(pphead &&*pphead);
//在这里不能直接删除第一个节点，这样就不能根据原本第一个节点的 next 指针找到原本第二个节点
//在头删方法中，只有一个节点和多个节点如下方法都可以实现
SLTNode* next =(*pphead)->next;//这里也是->的优先级大于*号
free(*pphead);
*pphead = next;
}
代码思路如下：
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x){
SLTNode* pcur = phead;
while(pcur){
if(pcur->data == x){
return pcur;
}else{
pcur = pcur->next;
}
}
returnNULL;
}
代码思路如下：
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x){
assert(pphead && pos);
//当 pos 为首节点的时候，会出现对空指针解引用的操作导致下面代码报错
//若 pos 直接等于*pphead 的时候则为头插，那么直接调用头插函数
if(pos ==*pphead){
SLTPushFront(pphead, x);
}else{
SLTNode* newnode = SLTBuyNode(x);
SLTNode* prev =*pphead;
while(prev->next != pos){
prev = prev->next;
}
newnode->next = pos;
prev->next = newnode;
}
}
注意：
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
//pos newnode -> (pos->next)
newnode->next = pos->next;
pos->next = newnode;
}
代码思路：
//删除 pos 结点
void SLTErase(SLTNode** pphead, SLTNode* pos){
assert(pphead && pos);
//要删除的节点就是头结点
if(pos ==*pphead){
SLTPopFront(pphead);
}else{
SLTNode* prev =*pphead;
while(prev->next != pos){
prev = prev->next;
}
//prev pos pos->next
prev->next = pos->next;
free(pos);
pos =NULL;
}
}
在下图我们要删除 2 节点（pos->next）
在上面操作中我们发现最后的 pos->next 指向 3 节点，也就是说最后释放的不是 2 而是 3 节点，所以我们需要定义 del 变量来存放 pos->next。
注意： 这里断言不能让 pos 指向空，也不能为尾节点，因为尾节点之后没有数据，无法删除。
//删除 pos 之后的结点
void SLTEraseAfter(SLTNode* pos){
assert(pos && pos->next);
SLTNode* del = pos->next;//pos del del->next
pos->next = del->next;
free(del);
del =NULL;
}
不能直接释放链表，应该一个一个释放链表里面的节点，这里不能直接释放节点，应该定义 pcur 保存该节点，并且还要保存下一个节点的地址，否则要销毁下一个节点的时候找不到该节点地址，变成野指针。
代码思路如下：
//销毁链表
void SListDestroy(SLTNode** pphead){
SLTNode* pcur =*pphead;
while(pcur){
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead =NULL;
}
在数据结构学习中，链表相对于顺序表而言有以下几个优势：
题目解释： 这道题题目很容易读懂，和上述我实现链表方法中的删除指定位置的节点意思类似，这里只需要给头结点就可以知道整个链表。
思路 1: 遍历链表找到值为 val 的结点，执行删除指定 pos 位置结点的操作，时间复杂度为 O(n^2)
思路 2: 创建新的链表，遍历原链表，将链表中值不为 val 的节点尾插到新链表中
注意： 这里不能使用双指针，因为双指针法只是修改节点里面的值却没有删除节点。
代码实现：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val){
//创建一个空链表
ListNode *newhead,*newtail;
newhead=newtail=NULL;
//遍历原链表
ListNode*pcur=head;
while(pcur){
//找值不为 val 的结点尾插到新链表中
if(pcur->val!=val){
if(newhead==NULL){
//链表为空
newhead=newtail=pcur;
}else{
//链表不为空
newtail->next=pcur;
newtail=newtail->next;
}
}
//遍历原链表
pcur=pcur->next;
}
if(newtail){
newtail->next=NULL;
}
return newhead;
}
题目解释： 这里只需将反转链表后的头结点给返回即可，题目意思很容易理解。
思路 1： 创建新链表，遍历旧链表中的节点拿过来头插
思路 2： 创建 3 个指针，n1 初始指向空，n2 指向头节点，n3 指向头节点下一个节点，只要 n2 的节点不为空，就让 n2 的 next 指针不指向 n3，改成指向 n1。然后让 n1 走到 n2 的位置，n2 走到 n3 的位置，n3 走到下一个节点的位置。一直重复直到 n2 为空结束该过程，n1 指向的节点即为头结点。
注意： 这里有特殊情况，若链表为空直接返回头结点即可，因为 n2 为头结点，n2 为空，那么 n2->next 是错误的，不能对空指针进行解引用。
代码实现：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head){
if(head==NULL){
return head;
}
ListNode*n1,*n2,*n3;
n1=NULL,n2=head,n3=n2->next;
while(n2){
n2->next=n1;
n1=n2;
n2=n3;
if(n3){
n3=n3->next;
}
}
return n1;
}
题目解释： 若链表里的节点是奇数个数，则直接返回该节点，如果节点是偶数个，那么返回第二个中间节点即可，这里题目描述很简单，但要注意节点是奇数个还是偶数个这两种情况。
思路 1： 求链表结点总数，除 2 求中间位置，返回中间位置结点 O（n）。在图 1 中，共有 5 个节点，5/2=2，定义 pcur 从 0 开始遍历，到 3 这个节点正好是下标为 2，即 3 是中间节点。
思路 2： 快慢指针，慢指针每次走一步，快指针每次走两步 即 2*慢指针=快指针。 在奇数节点个数中，若 fast->next=NULL，则不能往下走，slow 指向的节点 3 的位置就是中间节点。 在偶数节点个数中，fast=NULL 则不能往下走，slow 指向的节点 4 为中间节点。
这里判断节点是偶数个（fast=NULL）或者奇数个（fast->next=NULL）的时候，fast 和 fast->next 顺序不能相反，具体解释在代码中注释有。
注意：这里不能使用双指针向中间遍历，phead 可以向右遍历，因为存放 next 指针指向下一个节点，但是 ptail 不能往左走，因为没有存放前一个节点。
代码实现：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head){
ListNode*slow=head;
ListNode*fast=head;
while(fast&&fast->next){
//fast 和 fast->next 位置不能换，如果先 fast-> next，fast 都已经为空了，不能对空解引用
//代码会报错，只要第一个为假，就不会判断 fast->next 为真为假
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
题目解释： 题目给我们两个排好的升序链表，将他们连在一起合并成一个新的升序链表。
思路：
以上思路看起来是不是理所当然，但是当我们调试代码的时候报错了，下面的报错是不是很熟悉呀，我们根据他给的示例带入我们上述思路跑一下，l1 为空无法进入循环，直接跳到思路 5 中，新链表为空，其尾节点为空，不能对空进行解引用，我们的代码却让新节点的 newtail 的 next 指向 l2，所以报错。
我们根据上面问题发现是没有对链表为空进行处理，所以我们在思路 1 后面直接进行判断，若 l1 为空，直接返回 l2，同理 l2 也是如此。
在下面写代码时候我们发现思路中的步骤 3 判断链表是否为空，代码重复度过高，我们可以创建非空链表（malloc 节点大小空间，别忘记最后要释放哦），则不需要进行判空号，直接尾插。
代码实现：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
ListNode*l1=list1;
ListNode*l2=list2;
if(list1==NULL){
return list2;
}
if(list2==NULL){
return list1;
}
//新链表
ListNode*newhead,*newtail;
newhead=newtail=NULL;
while(l1&&l2){
if(l1->val<l2->val){
//l1 插入到新链表中
if(newhead==NULL){
//链表为空
newhead=newtail=l1;
}else{
newtail->next=l1;
newtail=newtail->next;
}
l1=l1->next;
}else{
//l2 插入到新链表中
if(newhead==NULL){
newhead=newtail=l2;
}else{
newtail->next=l2;
newtail=newtail->next;
}
l2=l2->next;
}
}
//跳出循环，只有两种情况，l1 走到空，l2 走到空
//有没有可能 l1l2 同时为空？不可能
if(l1){
newtail->next=l1;
}
if(l2){
newtail->next=l2;
}
return newhead;
}
题目解释： 如果两个链表相交则是相交链表，这里解释下啥是相交链表，若 l1 的某个节点和 l2 的某个节点相同，即是相交节点，有三种情况 l1 和 l2 的头结点就相同，l1 和 l2 中间有节点相同，l2 和 l3 的尾节点相同。
注意大家可能疑惑有没有 l1 和 l2 链表相交成'x'字型，答案是否定的，若交叉点为 n1，n1 的 next 节点只能存放一个地址，而不是多个，若两个链表相交，则从交叉点开始后面的节点均相同。
思路： 这里需要解决两个问题，1.如何判断链表是否相交 2.找相交的起始节点。
试错：一个个比较链表节点的 next 是否相等，这个方法仅限相交之前的节点个数相等（长度相同），所以该方法不行。
问题 1： 看尾节点的地址是否相同
问题 2： 找长度差，也就是找大小链表（求出两个链表的长度差），大链表先走长度差次，然后再一起比较两个链表的 next 是否相同。
代码实现：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* getIntersectionNode(struct ListNode*headA, struct ListNode*headB){
//求出两个链表的长度
ListNode*pa=headA,*pb=headB;
int sizeA=0,sizeB=0;
while(pa){
++sizeA;
pa=pa->next;
}
while(pb){
++sizeB;
pb=pb->next;
}
int gap=abs(sizeA-sizeB);//abs:求绝对值的函数
//让长链表先走 gap 步
ListNode*shortlist=headA;
ListNode*longlist=headB;
if(sizeA>sizeB){
longlist=headA;
shortlist=headB;
}
while(gap--){
longlist=longlist->next;
}
//shortlist longlist 在同一起跑线
while(shortlist){
if(shortlist==longlist){
return shortlist;
}
shortlist=shortlist->next;
longlist=longlist->next;
}
returnNULL;
}
题目解释： 链表带环如上图一样，它具有尾节点的 next 指向不为空的性质，若链表带环则返回 true 否则返回 false。
思路： 快慢指针（慢指针每次走一步，快指针每次走两步）：在环内追逐，若链表带环，快慢指针会相遇。
证明： 这里大家如果感兴趣可以自己证明或者在网上搜下为啥在环形链表中使用快慢指针，最终两指针会相遇！
代码实现：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode*head){
ListNode*slow=head,*fast=head;
while(fast&&fast->next){
slow=slow->next;
fast =fast->next->next;
if(slow==fast){
//相遇
return true;
}
}
return false;
}
题目解释： 这与上题类似，不过多解释。
思路： 这里还是快慢指针，但是要注意的是这里有个结论：相遇点到入环起始结点的距离等于链表头结点到入环起始结点的距离。
这里大家也可以自己证明下该结论如何成立的。
代码实现：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* detectCycle(struct ListNode*head){
ListNode*slow=head,*fast=head;
while(fast&&fast->next){
slow=slow->next;
fast=fast->next->next;
if(fast==slow){
//相遇点
ListNode*pcur=head;
while(slow!=pcur ){
slow=slow->next;
pcur=pcur->next;
}
return pcur;
}
}
returnNULL;
}
题目解释： 这道题提到我们要对这个链表进行深拷贝，这里我们要拷贝原链表中所有的数据，拷贝到一个全新的链表，即复制的链表中的指针不能指向原链表，藕断丝连。（该链表与普通节点不同的是额外添加了指针，该指针可以指向链表中的任何节点或空节点）
深拷贝：定义 pcur 指针指向当前节点，再来一个指针 pcur2 指向另外一个节点，但是该节点存储的值和前面一个节点存储的值相同，但是节点的地址互不相同（如图 1），简单理解就是把链表从一个地方拿到别的地方，链表里面存放到值完全一样，就是链表的位置即地址不一样而已。
浅拷贝：定义 pcur 指针指向当前节点，再来一个指针 pcur2 也指向该节点，它们使用的是同一块地址即浅拷贝（如图 2）。
代码思路： 这里大家可能想到把链表中除了 random 指针其他全部复制过来，然后再遍历原链表设置新链表的 random 指针，这个想法是正确的，但是我们发现置 random 指针很麻烦，无法处理。
思路 2：
注意：若链表为空需要特殊处理，直接返回即可。
代码实现：
/**
* Definition for a Node.
* struct Node {
* int val;
* struct Node *next;
* struct Node *random;
* };
*/
typedef struct Node Node;
//创建新节点
Node*buyNode(int x){
Node*node=(Node*)malloc(sizeof(Node));
node->val=x;
node->next=node->random=NULL;
return node;
}
void AddNode(Node*head){
Node*pcur=head;
while(pcur){
Node*next=pcur->next;
//创建新节点，插入到 pcur 结点之后
Node*newnode=buyNode(pcur->val);
newnode->next=pcur->next;
pcur->next=newnode;
pcur=next;
}
}
void setRandom(Node*head){
Node*pcur=head;
while(pcur){
Node*copy=pcur->next;
if(pcur->random){
copy->random=pcur->random->next;
}
pcur=copy->next;
}
}
struct Node* copyRandomList(struct Node* head){
if(head==NULL){
return head;
}
//1. 拷贝结点
AddNode(head);
//2. 置 random 指针
setRandom(head);
//3 断开链表
Node*pcur=head;
Node*newHead,*newTail;
newHead=newTail=pcur->next;
while(newTail->next){
pcur=newTail->next;
newTail->next=pcur->next;
newTail=newTail->next;
}
return newHead;
}
SList.h 源码
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//定义节点的结构
typedef int SLTDataType;
typedef struct SListNode {
SLTDataType data;
struct SListNode* next;
} SLTNode;
void SLTPrint(SLTNode* phead);
//尾插
void SLTPushBack(SLTNode**pphead, SLTDataType x);
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* pphead, SLTDataType x);
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode*pos , SLTDataType x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除 pos 节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
;
;
SList.c 源码
#include"SList.h"
void SLTPrint(SLTNode* phead){
//pcur 存放的是当前节点的地址
SLTNode* pcur = phead;
while(pcur){
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}
SLTNode* SLTBuyNode(SLTDataType x){
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if(newnode ==NULL){
perror("malloc fail!\n");
exit(1);
}
newnode->data = x;
newnode->next =NULL;
return newnode;
}
//尾插
void SLTPushBack(SLTNode**pphead, SLTDataType x){
//如果传来的是 NULL，那么不能解引用，所以需要断言 pphead 不能为空，但是*pphead 可以为空，因为它代表的是空链表，所以可以存在
assert(pphead);
//*pphead 就是指向第一个节点的指针
//空链表和非空链表两种情况
SLTNode* newnode = SLTBuyNode(x);
if(*pphead ==NULL){
*pphead = newnode;
}else{
SLTNode* ptail =*pphead;
//如果 ptail 为空，那么在循环里面不可以对空指针解引用，所以会报错
while(ptail->next){
ptail = ptail->next;
}
//ptail 指向的就是尾节点
ptail->next = newnode;
}
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x){
//空链表和非空链表都可以运行
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
newnode->next =*pphead;
*pphead = newnode;
}
//尾删
void {
assert(pphead &&*pphead);
((*pphead)->next ==)
{
(*pphead);
*pphead =;
}{
SLTNode* prev =*pphead;
SLTNode* ptail =*pphead;
(ptail->next){
prev = ptail;
ptail = ptail->next;
}
(ptail);
ptail =;
prev->next =;
}
}
{
assert(pphead &&*pphead);
SLTNode* next =(*pphead)->next;
(*pphead);
*pphead = next;
}
SLTNode* {
SLTNode* pcur = phead;
(pcur){
(pcur->data == x){
pcur;
}{
pcur = pcur->next;
}
}
returnNULL;
}
{
assert(pphead && pos);
(pos ==*pphead){
SLTPushFront(pphead, x);
}{
assert(pphead &&*pphead);
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
SLTNode* prev =*pphead;
(prev->next != pos){
prev = prev->next;
}
newnode->next = pos;
prev->next = newnode;
}
}
{
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
{
assert(pphead &&*pphead);
assert(pos);
(pos ==*pphead){
SLTPopFront(pphead);
}{
SLTNode* prev =*pphead;
(prev->next != pos){
prev = prev->next;
}
prev->next = pos->next;
(pos);
pos =;
}
}
{
assert(pos&&pos->next);
SLTNode* del = pos->next;
pos->next = del->next;
(del);
del =;
}
{
assert(pphead &&*pphead);
SLTNode* pcur =*pphead;
(pcur){
SLTNode* next = pcur->next;
(pcur);
pcur = next;
}
*pphead =;
}
test.c
#include"SList.h"
void test(){
//手动构造一个链表
SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
node1->data = 1;
node2->data = 2;
node3->data = 3;
node4->data = 4;
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next =NULL;
SLTNode* plist = node1;
SLTPrint(plist);
}
void test01(){
SLTNode* plist =NULL;
SLTPushBack(&plist,1);
SLTPushBack(&plist,2);
SLTPushBack(&plist,3);
SLTPushBack(&plist,4);
SLTPrint(plist);
//SLTPushFront(&plist, 1);
//SLTPushFront(&plist, 2);
//SLTPushFront(&plist, 3);
//SLTPushFront(&plist, 4);
//SLTPrint(plist);
//SLTPopBack(&plist);
//SLTPrint(plist);
//SLTPopBack(&plist);
//SLTPrint(plist);
//SLTPopBack(&plist);
//SLTPrint(plist);
//SLTPopBack(&plist);
//SLTPrint(plist);
////SLTPopFront(&plist);
//SLTPrint(plist);
//SLTPopFront(&plist);
SLTNode* find = SLTFind(plist,);
SListDestroy(&plist);
SLTPrint(plist);
}
val;
};
ListNode* {
ListNode* newHead,* newTail;
newHead = newTail =;
ListNode* pcur = head;
(pcur){
(pcur->val != val){
(newHead ==){
newHead = newTail = pcur;
}{
newTail->next = pcur;
newTail = newTail->next;
}
}
pcur = pcur->next;
}
newHead;
}
{
ListNode* node1 = (ListNode*)((ListNode));
ListNode* node2 = (ListNode*)((ListNode));
ListNode* node3 = (ListNode*)((ListNode));
ListNode* node4 = (ListNode*)((ListNode));
ListNode* node5 = (ListNode*)((ListNode));
ListNode* node6 = (ListNode*)((ListNode));
ListNode* node7 = (ListNode*)((ListNode));
node1->val = ;
node2->val = ;
node3->val = ;
node4->val = ;
node5->val = ;
node6->val = ;
node7->val = ;
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = node5;
node5->next = node6;
node6->next = node7;
node7->next =;
ListNode* plist = node1;
removeElements(plist,);
}
{
test02();
;
}
List.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int LTDatatype;
//定义双向链表（结点）结构
typedef struct ListNode {
LTDatatype data;
struct ListNode* next;
struct ListNode* prev;
} LTNode;
//初始化
LTNode* LTInit();
//void LTDesTroy(LTNode** pphead);
//接口一致性，传一级，在函数调用结束后需要手动将实参置为 NULL
void LTDesTroy(LTNode* phead);
//void LTInit(LTNode** pphead);
void LTPrint(LTNode* phead);
bool LTEmpty(LTNode* phead);
//尾插
//phead 节点不会发生改变，参数就为一级
//phead 节点发生改变，参数就为二级
void LTPushBack(LTNode* phead, LTDatatype x);
void LTPushFront(LTNode* phead, LTDatatype x);
//尾删
void LTPopBack;
;
;
;
LTNode* ;
List.c
#include"List.h"
LTNode* buyNode(LTDatatype x){
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
node->data = x;
node->next = node->prev = node;
return node;
}
LTNode* LTInit(){
//创建头结点
//LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
//phead->data = -1;
//phead->next = phead->prev = phead;
LTNode* phead = buyNode(-1);
return phead;
}
//void LTInit(LTNode** pphead)
//{
// assert(pphead);
// *pphead = (LTNode*)malloc(sizeof(LTNode));
// (*pphead)->data = -1;
// (*pphead)->next = (*pphead)->prev = *pphead;
//}
//void LTDesTroy(LTNode** pphead)
//{
// LTNode* pcur = (*pphead)->next;
// while (pcur != *pphead)
// {
// LTNode* next = pcur->next;
// free(pcur);
// pcur = next;
// }
// free(*pphead);
// *pphead = NULL;
//}
void LTDesTroy(LTNode* phead){
LTNode* pcur = phead->next;
while(pcur != phead){
LTNode* next = pcur->next;
free(pcur);
pcur = next;
}
free(phead);
phead =NULL;
}
void LTPushBack(LTNode* phead, LTDatatype x){
assert(phead);
LTNode* newnode = buyNode(x);
newnode->next = phead;
phead->prev->next = newnode;
phead->prev = newnode;
}
{
assert(phead);
LTNode* newnode = buyNode(x);
newnode->prev = phead;
phead->next->prev = newnode;
phead->next = newnode;
}
{
LTNode* pcur = phead->next;
(pcur != phead){
(, pcur->data);
pcur = pcur->next;
}
();
}
{
assert(phead);
phead->next == phead;
}
{
assert(!LTEmpty(phead));
LTNode* del = phead->prev;
del->prev->next = phead;
phead->prev = del->prev;
(del);
del =;
}
{
assert(!LTEmpty(phead));
LTNode* del = phead->next;
del->next->prev = phead;
phead->next = del->next;
(del);
del =;
}
LTNode* {
LTNode* pcur = phead->next;
(pcur != phead){
(pcur->data == x){
pcur;
}
pcur = pcur->next;
}
returnNULL;
}
{
assert(pos);
LTNode* newnode = buyNode(x);
newnode->next = pos->next;
newnode->prev = pos;
pos->next->prev = newnode;
pos->next = newnode;
}
{
assert(pos);
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
(pos);
pos =;
}
test.c
#include"List.h"
void test(){
//LTNode* plist = NULL;
//LTInit(&plist);
LTNode* plist = LTInit();
LTPushBack(plist,1);
LTPushBack(plist,2);
LTPushBack(plist,3);
LTPushBack(plist,4);
//LTPushFront(plist, 1);
//LTPushFront(plist, 2);
//LTPushFront(plist, 3);
//LTPushFront(plist, 4);
LTPrint(plist);
//4 3 2 1
////LTPopBack(plist);
//LTPrint(plist);
//LTPopBack(plist);
//LTPrint(plist);
//LTPopBack(plist);
//LTPrint(plist);
//LTPopBack(plist);
//LTPrint(plist);
////LTPopFront(plist);
//LTPrint(plist);
//LTPopFront(plist);
//LTPrint(plist);
//LTPopFront(plist);
//LTPrint(plist);
//LTPopFront(plist);
//LTPrint(plist);
//LTPopFront(plist);
//LTPrint(plist);
//LTNode* find = LTFind(plist, 3);
//if (find == NULL)
//{
// printf("ûҵ\n");
//}
//else {
// printf("ҵˣ\n");
//}
//LTInsert(find, 99);
//LTErase(find);
//LTPrint(plist);
LTDesTroy(plist);
plist =;
}
{
test();
;
}
链表作为数据结构中的重要线性结构，其灵活的存储方式和高效的插入删除操作使其在众多场景中不可或缺。本文从链表的基本概念入手，详细解析了链表的分类方式，通过手动实现单链表的各项核心操作，深入剖析了指针操作的细节与边界条件的处理，尤其对二级指针的使用场景和原理进行了重点说明。
在此基础上，通过对比顺序表，凸显了链表在头部操作、空间利用等方面的优势，并结合 8 道经典 OJ 题，展示了链表在实际问题中的应用技巧，如快慢指针、新链表构建、环形链表特性利用等。最后提供的单链表和双链表完整源码，为实践练习提供了直接参考。
掌握链表不仅是理解更复杂数据结构（如哈希表、树、图）的基础，其指针操作逻辑也能显著提升对内存管理和程序设计的理解。希望本文能帮助读者扎实掌握链表知识，为后续数据结构学习和算法提升奠定坚实基础。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online