当前位置：首页 > news >正文

长春财经学院汕头seo优化培训

news 2025/7/6 11:48:22

长春财经学院,汕头seo优化培训,建站之星网站登录,网站建设策划方案书希望文章能对你有所帮助，有不足的地方请在评论区留言指正,一起交流学习! 目录 1.链表 1.1 链表概念和组成 1.2 链表的分类 1.3 顺序表和链表 2.单链表（无头单向不循环链表） 2.1 结点的创建 2.2 创建新的结点 2.3 单链表的打印 2.4 尾…

希望文章能对你有所帮助，有不足的地方请在评论区留言指正,一起交流学习!

1.链表

1.1 链表概念和组成

1.2 链表的分类

1.3 顺序表和链表

2.单链表（无头单向不循环链表）

2.1 结点的创建

2.2 创建新的结点

2.3 单链表的打印

2.4 尾插和尾删

2.5 头插和头删

2.6 查找函数

2.7 在pos之前插入和pos位置的删除

2.8 在pos之后插入和删除

3.单链表的OJ题目

4.带头循环双向链表

本文将介绍详细介绍链表中的不带头单向不循环链表（单链表）和带头双向循环链表的增删查改（使用），以及关于单链表的OJ题的分析和答案。

1.链表

本部分介绍链表的概念以及组成、分类。

1.1 链表概念和组成

链表是在存储空间是不连续的，但是每个数据结点是通过结点中的指针连接的。

下图是一个单链表存储的数据类型是整型，plist存储的链表的第一个结点的位置，通过第一个结点，可以通过结点中存储的指针访问下一个结点的内容。最后一个结点存储的指针是空的。

上图的结点创建通过结构体创建如下

//定义结点中存储的数据的类型
typedef int SLTDataType;
//创建结点内容 
struct SListNode
{SLTDataType data;            //数据域 节点中存在的数据struct SListNode * next;	 //指针域 域指向下一个节点的指针
};

结点一般有数据域和指针域组成，数据域存储的是链表所存储的数据，可以是结构体、整型等等数据类型；指针域，结点中可能有两个指针（双向链表，分别指向链表的前后结点）或者一个指针（单向链表，指向链表的下一个结点）。总之，链表由结点构成，结点中存储着数据以及连接链表的指针。

1.2 链表的分类

链表和顺序表一样数用来存储数据的一种结构，链表分为8种，有单向、双向；带头、不带头；循环、不循环之间组合。分别是带头单向循环、带头单向不循环、带头双向循环、带头双向不循环、不带头单向不循环、不带头单向循环、不带头双向不循环、不带头双向循环。

先从简单的单向开始说起

1）单向不带头不循环链表（d1、d2……代表数据）空白代表指针（这里不在编写指针，理解即可）

2）单向带头不循环链表

带头和不带头的相同长度的链表，就是多一个结点，这个结点可以叫做哨兵位，哨兵位结点存储是链表起始结点的指针，结点类型和存储数据的结点一样。当链表中没有数据存储的时候，

guard->next = NULL 对比不带头的链表在链表为空的状态下存储数据的时候省去了判断链表是否为空的步骤。

3）单向不带头循环链表

相比不循环就是多了一个圈，这个圈从来链表的结尾执行链表的起始地址，和链表中的环不一样（下面会有详细介绍链表环）。

4）单向带头循环链表

5）双向不带头不循环链表

和单向不同的是双向链表有两个指针，可以指向两个方向就是双向了，下面就就是结点的创建，两个指针，在插入和删除操作时，逻辑简单，便于操作。

//定义结点中存储的数据的类型
typedef int SLTDataType;
//创建结点内容 
struct SListNode
{SLTDataType data;            //数据域 节点中存在的数据struct SListNode * next;	 //指针域 指向下一个结点struct SListNode * prev;	 //指针域 指向上一个结点
};

6）双向不带头循环链表

和单向循环双向循环多了一个循环回路，有头结点的prev指向尾部结点，尾部的next指向头部的结点。

7）双向带头不循环链表

8）双向带头循环链表

9）单链表和双向带头循环链表的比较

由最初的单链表（单向不带头不循环）到最后的双向带头循环链表，看着结构逻辑更加的复杂了，但是后者的程序更加好编写，在后续的学习中大家可以体会的到，

二者相比

单链表的结构简单，但在程序编写复杂，在接口的形参上，大部分需要传递是二级指针；且部分函数编写无法进行复用，在数据存储和调用上需要逐步遍历寻找，因此也不会单独存储数据，更多的是使用在其他数据结构的底层中，如哈希桶

带头双向循环链表，结果较为复杂，但是程序好编写，由于一个结点两个指针的情况，在加入和删除数据的操作简单，因此适合存储数据；在形参的传递上仅需要传递一级指针即可，无论头部和尾部的插入和删除接口均可以复用函数实现。

1.3 顺序表和链表

顺序表是内存是连续存储的，链表的内存在逻辑上是连续存储的；

顺序表的内存申请的会造成一定成的内存浪费，链表是按需申请；

顺序表的使用realloc函数开辟空间，异地开辟的情况，重新迁移数据，浪费时间，且浪费空间，链表均为小块的空间通过指针连接。

总之，顺序表和链表各有各的好处，只是两者的用途不同。

2.单链表（无头单向不循环链表）

本部分将详细介绍单链表中对数据的增删查改，分析其中的思路并给出示例。数据以整型为例。

2.1 结点的创建

在上文中提到结点由指针和存储的数据构成，使用结构体来创建的结点，因此就要结点的指针要使用结构体指针指向下一个结构体（结点）；数据类型重新定义名称方便的后续的修改。

//定义结点中存储的数据的类型
typedef int SLTDataType;
//创建结点内容 
struct SListNode
{SLTDataType data;            //数据域 节点中存在的数据struct SListNode * next;	 //指针域 域指向下一个节点的指针
};
typedef struct SListNode SLTNode //将结构体类型重新定义为简单的表达，便于使用

2.2 创建新的结点

链表在使用过程中需要加入新的结点，就需要新的结点；结点函数形参为存储到结点的数据，返回值为新的结点的指针。创建新的结点，首先使用malloc为新的结点开辟空间，然后再给结点的中的data赋值，将结构体中的next指针置为NULL。

SLTNode* BuyNewNode(SLTDataType x)
{//创建新的节点SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//判断空间是否开辟成功if (newnode == NULL){perror("malloc fail");}//赋值newnode->data = x;newnode->next = NULL;return newnode;
}

2.3 单链表的打印

单链表的打印，建议使用新的指针（cur，current 当前的）将链表的头指针（指向首个结点的指针），为什么遍历的条件结束的条件是cur ！= NULL 而不是cur->next ！=NULL呢？可以分析当cur->next为空的时候，cur刚刚指向最后一个指针。此时循环结束，未遍历所有的结点数据，

cur = cur->next 此行代码保证了链表的依次向后遍历数据。当链表为空的时候，phead可能为NULL，因此这里不能使用assert（phead）来判断链表是否为空，也可以使用来判断链表是否为空。

//输出链表顺序
void SLTPrintf(SLTNode* phead)//phead是链表指向链表的开端，链表的最后一个节点的的存储的指针是NULL
{//assert(phead);SLTNode* cur = phead;//创建一个新的节点，赋值while (cur != NULL){printf("%d->",cur->data);cur = cur->next;}printf("NULL\n");
}

当cur=NULL的时候，循环停止。

2.4 尾插和尾删

代码中的注释较多，在次简单说一下思路和注意事项

尾插函数：分为两种情况，

一种空链表，phead（链表的头指针:指向链表的第一个结点）

我们在创建新的结点的时候，将结点的next置为NULL，因此尾插的时候不用考虑它，只需要考虑将phead指向newnode。

本次要修改的是phead，如果传递的是一级指针和phead同级，无法对phead修改，所以要传递二级指针。所以*pphead= phead，如下图经过指令*pphead = newnode之后

另一种情况就比较难一些了，首先我们需要找到尾部，找到之后再将新的结点插入。

找到尾部，我们需要使用while循环遍历整个链表，但是和遍历打印不同的是判断条件是

tail->next != NULL；为什么？循环遍历不一样导致cur和tail结束的位置不一样，在打印遍历的时候cur的位置最后指向的是NULL，而这里的遍历条件tail结束的的时候指向的是最后的结点。

当找到最后一个结点的时候就要将tail和newnode连接起来了，根据结点的指向，tail的几点中的next应该指向newnode 结点，因此tail->next=newnode，可以将tail指向的结点和newnode指向的结点连接。

//尾插函数
void SLTPushBack(SLTNode** pphead,SLTDataType x)
{assert(pphead);//传递的是结构体指针，SLTNode* newnode = BuyNewNode(x);//将上述节点加在尾部//分为两种情况 一种为链表为空，一种是链表不为空if (*pphead == NULL){*pphead = newnode;//将新开辟的节点指针赋值给链表首地址}else{SLTNode* tail = *(pphead);//对传递过来的数据进行修改 while (tail->next != NULL){tail = tail->next;}//找到尾部后，将尾部的NULL替换为新节点的指针tail->next = newnode;}
}

尾删函数

此函数中可能涉及到phead头指针的修改，例如链表中只有一个元素，删除之后链表可能为空，所以就要将phead = NULL。综上所属，函数的形参需要传递的是二级指针。

尾删分为三种情况，看图解吧，比较直观。

首先第一种情况 链表为空的情况使用assert（*pphead）直接进行空指针判断是否为空。

第二种情况：链表中只有一个结点的情况，将phead直接置为NULL，则链表为空。这里的

*pphead修改才能真正的修改到phead。

第三种情况：链表中有两个以及两个以上的元素，通过遍历递进找到链表最后一个结点的上一个结点。判断的遍历循环的结束条件是tail->next->next != NULL，循环结束的时候 tail指向的是倒数第二个结点，

将tail指向的这个结点的tailnext=NULL，就可以将最后一个结点和之前结点的指针连接断开。

当然在删除掉结点的时候一定要将结点申请的空间释放掉，需要的是指向内存的的指针，即

free(tail->next)要在置为NULL之前使用，防止内存泄漏。

//尾删函数
void SLTPopBack(SLTNode** pphead)
{assert(pphead);//判断pphead是否为空assert(*pphead);//若链表为空，则直接报错//一个节点的情况下if ((*pphead)->next==NULL){free(*pphead);*pphead = NULL;}else {//找尾多个节点SLTNode* tail = *pphead;while (tail->next->next != NULL)//寻找的是下一个节点是否为最后一个节点{tail = tail->next;}//当找到位置的时候，free(tail->next);tail->next = NULL;}
}

2.5 头插和头删

头插函数

在这里也要考虑两种情况，一种链表为空，一种链表不为空，如下图。和尾插不同的值这里不用再遍历链表了。

链表为空的情况和尾插一样的:

链表不为空的情况:分为两个步骤看图吧，第一步要插入结点肯定要创建结点，新的结点的指针名字为plist。

第二步，将新的结点的next指向第一个结点，plist->next = *pphead;
第三步将原本的头指针phead（*pphead）改为指向plist*pphead = plist。

//头插函数
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{//考虑两种情况 链表有数据 链表没有数据，assert(pphead);//判断是否为空指针//先创建一个新的节点 插入SLTNode* plist = BuyNewNode(x);//链表为空的情况下if(*pphead==NULL)*pphead = plist;//链表有数据的情况下else {plist->next = *pphead;*pphead = plist;}
}

头部删除

两种情况一种链表为空，另种情况链表不为空

对于链表为空的状态，使用了assert（*pphead）直接报错的；

对于链表不为空的情况（包含链表种只有一个元素的情况）

上图由*pphead = (*pphead)->next;操作由红色虚线变为蓝色虚线；然后释放删除结点的空间 free(head); head = NULL。


//头删函数
void SLTPopFront(SLTNode** pphead)
{assert(pphead);//检测是否为空指针assert(*pphead);//链表为空的情况下//链表有多个节点SLTNode* head = *pphead;//创建临时指针 便于后续释放节点申请的空间*pphead = (*pphead)->next;free(head);head = NULL;}

2.6 查找函数

函数的形参的确定，再查找函数中，不会涉及对函数头指针以及结点（结构体的修改），因此传递二级指针，还有需要寻找的元素的数值（以整型为例）为形参。需要注意的是结点的返回值。

思路：遍历链表寻找具有相同的值的元素。这里循环结束的条件是ptr！=NULL；即ptr会走到NULL的位置结束。

在链表种没有找到元素的时候，返回NULL；链表为空，使用的assert（phead）判断是个否为空；

链表不为空的状态,没有做动图，大家将就一下，后面等我调试好软件改以一下。

//查找函数
SLTNode* SlistFind(SLTNode* phead, SLTDataType x)
{assert(phead);//查找函数考虑是否是空链表SLTNode* ptr = phead;while (ptr != NULL){if (ptr->data == x){return ptr;}else{ptr = ptr->next;}}return NULL;//空指针的情况下/*SLTNode* prev = phead;while (prev->next->data != x){prev = prev->next;}return prev->next;*/
}

2.7 在pos之前插入和pos位置的删除

在pos位置之前插入

函数的形参，以插入的结点的位置，插入结点的数据，链表头的二级指针（修改链表头）；分为两种情况，其实在前面的SlistFind（）函数种，我已经使用assert（phead）将空链表的情况排除了。

第一种情况，pos指向phead，plist是前插函数创建的结点，下图的操作是红色的建有改为了蓝色的箭头

第二种情况pos指向其他位置，首先创建prev变量，根据判断条件prev->next!=pos找到得指针prev指向得是pos位置得前一个结点。

找到位置之后就可以创建新的结点，然后插入。详细过程如图：

//pos位置之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);//判断传递的指针是否为空assert(pos);//在数据中间插入if (pos == *pphead){SLTPushFront(pphead, x);//在空指针的情况下，直接插入}else{//创建新的节点SLTNode* newnode = BuyNewNode(x);SLTNode* prev = *pphead;//保证原来指针不要修改while (prev->next != pos){prev = prev->next;}prev->next = newnode;newnode->next = pos;}}

删除pos位置结点

由于删除pos位置之前的结点，容易造成非法访问，不便于操作，因此直接删除pos位置的结点。

两种情况，一种为pos指向第一个结点，一个为pos不指向第一个结点。

第一种情况相当于头删，直接调用的头删函数就可以了。

第二种情况遍历寻找到pos位置之前的结点，然后修改结点的指针。

//删除pos位置结点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);if (pos == *pphead){SLTPopFront(pphead);}else //pos != *pphead{SLTNode* prev = *pphead;//创建新的节点寻找poswhile (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;//pos传递的是一级指针，在这里修改无用，应在主函数中修改}}

2.8 在pos之后插入和删除

思路：

在pos之后插入新的结点

在pos之后插入新的结点操作较为简单，只需要修改指针的指向即可。

首先创建新的结点，因为在确定位置之后的尾插在这里不用考虑头指针的修改，所以不用传递phead，pos和x即可。然后交换newnode和pos结点的next即可完成交换


//pos位置之后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);//创建新的节点SLTNode* newnode = BuyNewNode(x);//插入 交换指针newnode->next = pos->next;pos->next = newnode;}

提示： 在pos之后删除新的结点，传递的形参只用pos指针就可以了，考虑到pos为尾结点的时候报错。

//pos位置之后的删除
void SLTEraseAfter( SLTNode* pos)
{assert(pos->next);//判断pos是否为尾结点SLTNode* del = pos->next;pos->next = del->next;free(del);//del = NULL;
}

在pos之前插入和在pos之后插入的时间复杂度比较，之前为O（N），之后插入为O(1)，因此在确定位置的插入，单链表也适合尾部插入。

3.单链表的OJ题目

本部分包含单链表的OJ题目，其中会有使用带哨兵位的链表的使用（带头的单向链表）。此章节不会所有的题都有图，看代码可以看懂思路的不会有图。

3.1 删除链表等于给定值val的结点

题目连接：203. 移除链表元素 - 力扣（LeetCode）

和单链表中删除指定位置pos的操作相同，对于给定的val值找出对应的结点，然后删除结点。不同的是操作要遍历整个链表，因此结束条件是head=NULL。当然我还是会有绘图的。

1. 首先按照给定的值找到对应结点，创建新的指针cur=head，哟哦与返回值是链表的头指针，不便于修改head。

2.如何将对应的cur指向的结点删除，分两种种情况，一种cur是首结点，涉及到head，修改的时候较为麻烦；另一种是其他结点（包含尾结点），根据2.7中写的删除对应结点位置的指针，使用两个指针，cur前面的指针也要确定，因此需要定义另一个指针为prev。

1.寻找结点cur 当然寻找结点和删除结点时同步进行的

2. 删除对应val的结点，分为两种情况；一种情况是phead = cur（题目中的头指针是head）的情况， 需要修改头指针；第二种情况 删除指定结点操作。

上面是对于写思路的分析，下面是代码。

struct ListNode* removeElements(struct ListNode* head, int val) 
{struct ListNode* prev = NULL;struct ListNode* cur = head;while(cur)//遍历的循环条件 cur！=NULL{if(cur->val != val)  //在不是val值的情况{prev = cur;cur = cur->next;//prev->next = cur 意思是prev的next指向cur}else {if(prev == NULL)// val是第一结点{head = cur->next;//删除第一个结点的操作free(cur);cur = head;}else                 //val不是第一个结点{prev->next = cur->next;free(cur);cur = prev->next;}}}return head;
}

按照之前的说法想要修改头指针的情况就要传递二级指针，但是这里由返回值，返还的是修改之后的值，因此这里传递一级指针足够。当然函数种知道删去结点的指针，可以使用free函数释放归还操作空间，但是无法将其置为空，在同一级的指针种，形参的改变无法改变实参。

3.2 反转一个单链表

题目连接：206. 反转链表 - 力扣（LeetCode）

提示：和单链表种的头插的操作相似，创建一个新的链表将上面的链表按下顺序从第一个结点依次头插如新的结点。

struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* newhead = NULL;//新的链表的头结点指针struct ListNode* cur = head;//在子函数中，形参的数最好不修改，保证可用while(cur != NULL){struct ListNode* next = cur->next;//存储指针，方便指针的更迭//头插cur->next = newhead;newhead = cur;cur = next;}return newhead;
}

3.3 寻找链表的中间结点

描述：给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

题目链接：876. 链表的中间结点 - 力扣（LeetCode）

提示：使用两个指针来遍历链表，快慢指针思路，一个依次走两步，一个一次走一步。

分为两种情况

奇数个结点 fast（快指针）走到尾结点就结束了，判断条件是 fast->next!=NULL
偶数个结点 fast（快指针）走到NULL的时候才结束，判断条件是 fast！=NULL

偶数结点

奇数结点

struct ListNode* middleNode(struct ListNode* head) 
{struct ListNode* slow = head; //慢指针struct ListNode* fast = head; //快指针while(fast && fast->next){//移步slow = slow->next;     fast = fast->next->next;}return slow;
}

3.4 返回倒数第k个结点

题目链接：面试题 02.02. 返回倒数第 k 个节点 - 力扣（LeetCode）

提示：使用快慢指针，快指针走k步，当快指针为NULL的时候（画图分析），慢指针正好位于倒数第k个结点。

int kthToLast(struct ListNode* head, int k)
{struct ListNode* fast = head;struct ListNode* slow = head;while(k--){fast = fast->next;}while(fast){fast = fast->next;slow = slow->next;}return slow->val;
}

3.5 合并两个有序链表

题目链接：21. 合并两个有序链表 - 力扣（LeetCode）

提示：创建一个新的链表，然后比较大小，依次尾插进入新的链表中，会剩余一个链表还有结点，直接将新的链表和有剩余结点的链表链接起来。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {//判断链表是否为空if(list1 == NULL)return list2;if(list2 == NULL)return list1;struct ListNode* cur1 = list1;struct ListNode* cur2 = list2;struct ListNode* head = NULL;struct ListNode* tail = NULL;//  创建一个新的链表赋值while(cur1 && cur2){if(cur1->val < cur2->val){//插入的为第一个元素 尾插if(head == NULL){  tail = head = cur1;}  else{tail->next = cur1;tail = tail->next;}cur1 = cur1->next;}else{//插入的为第一个元素 尾插if(head == NULL){  tail = head = cur2;}  else{tail->next = cur2;tail = tail->next;}cur2 = cur2->next;}//处理剩余结点if(cur1){tail->next = cur1;}if(cur2){tail->next = cur2;}return head;
}

3.6

3.7

3.8

3.9 * 给定一个链表，判断链表中是否有环（含只有证明）

题目链接：141. 环形链表 - 力扣（LeetCode）

思路；快慢指针，等快指针和慢指针相等的时候，链表肯定存在环；如果使用的是链表中存在的数据相等，无法证明链表有环的，链表中含有重复的数值。

bool hasCycle(struct ListNode *head) {struct ListNode *slow = head;struct ListNode *fast = head;struct ListNode *cur = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if(fast == slow)return true;}return false;
}

bool 布尔值，真的情况下，返回 true 错误的情况下，返回 false。

证明

1.为什么fast走2步，slow走1步，二者会相遇，不会错过吗？