目录

一、顺序表的问题及思考

二、单链表

2.1链表的概念及结构

2.2.单链表的实现

2.2.1.节点的定义

2.2.2.链表的打印

2.2.3.头部插入删除/尾部插入删除

a.创建节点

b.尾插

c.头插

d.尾删

e.头删

2.2.4.查找数据

2.2.5.在指定位置之前插入数据

2.2.6删除pos节点

2.2.7在指定位置之后插入数据

2.2.8删除pos之后的节点

2.2.9销毁链表

三、链表OJ

3.1移除链表元素

思路一：

思路二：

3.2反转链表

思路一：

思路二：

3.3链表的中间结点

思路一：

思路二：

3.4合并两个有序链表

思路：

优化：

3.5环形链表的约瑟夫问题

思路：

3.6分割链表

思路一：

思路二：

思路三：

四、链表的分类

4.1链表说明

五、双向链表

5.1双向链表的实现

5.1.1.节点的定义

5.1.2链表打印

5.1.3申请节点与初始化

5.1.4尾插

5.1.5头插

5.1.6尾删

5.1.7头删

5.1.8查找节点

5.1.9在指定位置之后插入数据

5.1.10删除指定节点

5.1.11判空

5.1.12销毁节点

---

一、顺序表的问题及思考

1.顺序表进行中间/头部的数据的插入删除操作时，由于顺序表的底层是数组，为了实现对应的操作，我们需要挪动对应数据之后所有其他数据，这就导致这一步操作的时间复杂度为O(N)，这么一看，为了实现这一功能，我们似乎付出了很大的代价。

2.顺序表增容需要申请新空间，拷贝数据，释放旧空间，这会有不小的消耗。

3.增容⼀般是呈2倍的增长，势必会有⼀定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

思考：如何解决以上问题呢？针对上诉的种种问题，链表诞生。

二、单链表

2.1链表的概念及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表
中的指针链接次序实现的 。链表也是线性表。

链表的结构跟火车车厢相似，淡季时车次的车厢会相应减少，旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉/加上，不会影响其他车厢，每节车厢都是独立存在的。链表也是这样的，链表每一个节点之间相互独立，我们可以按需申请或释放任意节点，增加或删减某一节点不会影响其他节点。

对于火车，车厢是独立存在的，且每节车厢都有车门。想象一下这样的场景，假设每节车厢的车门都是锁上的状态，需要不同的钥匙才能解锁，每次只能携带一把钥匙的情况下如何从车头走到车尾？

最简单的做法：每节车厢里都放一把下一节车厢的钥匙。

在链表里，每节“车厢”是什么样的呢？

与顺序表不同的是，链表里的每节"车厢"都是独立申请下来的空间，我们称之为“结点/节点”（两种称呼都可）节点的组成主要有两个部分：当前节点要保存的数据和保存下⼀个节点的地址（指针变量）。 图中指针变量plist保存的是第⼀个节点的地址，我们称plist此时“指向”第⼀个节点（不能称呼头结点），如果我们希望plist“指向”第二个节点时，只需要修改plist保存的内容为0x0012FFA0。

为什么还需要指针变量来保存下⼀个节点的位置？因为链表中每个节点都是独立申请的（即需要插入数据时才去申请⼀块节点的空间），每个节点之间物理地址上没有关系，我们需要通过指针变量来保存下⼀个节点位置（地址）才能从当前节点找到下⼀个节点。每个节点通过这样的方式在逻辑上串联在一起。

结合前面学到的结构体知识，我们可以给出每个节点对应的结构体代码： 假设当前保存的节点为整型：

struct SListNode
{int data; //节点数据 struct SListNode* next; //指针变量⽤保存下⼀个节点的地址 
};

当我们想要保存⼀个整型数据时，实际是向操作系统申请了⼀块内存，这个内存不仅要保存整型数 据，也需要保存下⼀个节点的地址（当下⼀个节点为空时保存的地址为空）。 当我们想要从第⼀个节点走到最后⼀个节点时，只需要在前⼀个节点拿上下⼀个节点的地址（下⼀个 节点的钥匙）就可以了。（需要注意的是，我们通过结构体内的指向下一节点的指针变量来保存下一节点的地址，而不是直接在结构体存储结构体变量，因为我们还在定义节点的结构，而结构体内存结构体会造成套娃而导致一些严重后果。）

补充说明：
1、链式结构在逻辑上是连续的，在物理结构上不一定连续。
2、节点一般是从堆上申请的
3、从堆上申请来的空间，是按照一定策略分配出来的，每次申请的空间可能连续，可能不连续

2.2.单链表的实现

2.2.1.节点的定义

在定义节点存储数据类型时，我们想保存的数据类型可能为整形，字符型、浮点型或者其他自定义的类型，因此，为了适应不同情形下，存储数据的不同，我们为要存储的数据起别名，定义时直接使用别名。

typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data; //节点数据
struct SListNode* next; //指针保存下一个节点的地址
}SLTNode;

2.2.2.链表的打印

链表的打印
void SLTPrint(SLTNode* phead)
{SLTNode* pcur = phead;while(pcur)//pcur遍历链表{printf("%d->",pcur->data);打印节点中的数据pcur = pcur->next;//指针移动到下一个节点}printf("NULL\n");最后一个节点指向NULL,打印NULL
}

为了能够访问到对应节点及整个链表。我们通常将有效节点的地址传递到函数中（比起直接传节点效率更高）。一般情况下，为了之后仍然能够获得第一个有效节点的位置，我们创建一个指针，并通过这个指针来遍历整个链表。节点中的next指针存储着下一个节点的地址，一个链表的尾节点由于没有下一个节点，next指针中存储NULL值，我们将其作为循环结束条件，pcur为空指针，说明链表走完了。每次访问完一个节点的数据，我们就需要利用节点next存储的地址，将pcur指针移动到下一节点。

2.2.3.头部插入删除/尾部插入删除

a.创建节点

SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode*newnode = (SLTNode*)malloc(sizeof(SLTNode));if (NULL == newnode){perror("malloc failed");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}

进行插入之类的操作时，我们需要创建新节点，为避免重复操作，我们在这里封装一个函数。

b.尾插

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);//*pphead 就是指向第一个节点的指针//空链表和非空链表SLTNode* petail = NULL;if(NULL == *pphead){*pphead = SLTBuyNode(x);}else{//找尾petail = *pphead;while(petail->next){petail = petail->next;}//ptail指向的就是尾节点petail->next = SLTBuyNode(x);}
}

进行对链表的操作，我们不能传入一个NULL空指针，应该传入一个指向有效链表的地址（包括空链表）。链表的尾插是通过将尾节点的next由指向NULL改为指向新节点newnode，这样逻辑上新节点就串进链表中。首先我们需要先将petail指针通过循环移动到尾节点，需要注意的是循环终止条件不能是while（petail）,因为这是petail通过尾节点的next，此时指向NULL,并不是尾节点，尾节点的next指向NULL,我们将这个作为循环终止条件。跳出循环我们将petail->next = SLTBuyNode,链表创建完成。

需要注意的是，链表存在为空时，因此当链表为空，petail->next作为循环终止条件会出现问题，

因此，我们需要单独处理链表为空的情况，这时新的节点作为第一个有效节点。但是这是会出现一个问题，由于函数形参是传值拷贝，如果函数参数是传递一级指针phead，那么函数调用完，指向链表的第一个有效节点的头指针本身指向无法改变，它仍然指向NULL，这就导致野指针的问题，因此，传递参数，我们传递二级指针（pphead）来改变函数外部的指针指向。（后续节点都是通过前一个指针内部存储的地址访问的，不会出现上诉问题。）

c.头插

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);//newnode *ppheadnewnode->next = *pphead;*pphead = newnode;
}

我们创建新节点，将新节点的next指向原链表第一个有效节点，然后将原来的头指针指向新节点，为了修改头指针，我们传递二级指针。与尾插类似，头插同样存在链表为空的情况，但是插入时都是插入新节点作为第一个有效节点，因此，链表为空的情况不需要特殊处理（原链表为空，则新节点指针指向next）。

d.尾删

void SLTPopBack(SLTNode** pphead)
{//链表不能为空assert(pphead && *pphead);//链表只有一个节点if ((*pphead)->next == NULL)//->优先级高于*{free(*pphead);*pphead = NULL;}else {//链表有多个节点SLTNode* prev = *pphead;SLTNode* ptail = *pphead;while (ptail->next){prev = ptail;ptail = ptail->next;}//prev ptail;free(ptail);ptail = NULL;prev->next = NULL;}
}

对于链表的节点进行删除操作，首先需要明确的是我们不能传入NULL，而不能传入空链表（已经是空不能再删除。）,同时我们也不能传入，进行链表尾删时，我们需要通过循环遍历找到尾节点（ptail->next指向NULL，就说明指向尾节点），然后将其释放，这是它的前一个节点成为新的尾节点，我们需要将其next指针指向NULL,因此我们需要创建一个指针记录链表尾节点的前一个节点。

此外对于链表中只有一个节点存在的情况，ptail->next指向NULL,循环结束，ptail与prev指向同一节点，释放ptail,prev变成野指针，prev->next就出现解引用野指针的情况。因此当链表仅有一个节点时，我们直接释放，置空。

e.头删

void SLTPopFront(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}

进行头删操作时，释放第一个有效节点之前，我们需要创建指针记录第一个有效节点的next指向的下一节点，这样当我们释放完后，我们可以找到第二个节点，将头指针指向它。否则会出现对野指针的解引用。

2.2.4.查找数据

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{assert(phead);SLTNode* pcur = phead;while(pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}

循环遍历，将所给值与pcur->data比较，如果相等，返回节点，跳出循环。循环遍历完都找不到，返回NULL。

2.2.5.在指定位置之前插入数据

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead && *pphead);assert(pos);SLTNode* newnode = SLTBuyNode(x);SLTNode* pcur = *pphead;if (pos == *pphead){SLTPushFront(pphead, x);}else{while (pcur->next != pos){pcur = pcur->next;}newnode->next = pcur->next;pcur->next = newnode;}}

因为不需要改变外部的指针，只是指定插入位置，这里我们不需要传入二级指针。我们通过pcur->next != pos作为循环遍历终止条件，找到插入位置的前一个节点，我们先将新节点的newnode->next 指向插入位置pcur的下一节点，然后再将pcur->next 指向newnode，这两步不能颠倒，否则，我们无法知道插入位置处节点下一节点。

当插入位置为NULL,代码逻辑没有问题。

当在链表的第一个有效节点之前插入，pos = *pphead代码逻辑出现问题,因此对于这一情况，我们需要特殊处理，我们发现这一情况逻辑与头插一致，我们调用头插函数。

2.2.6删除pos节点

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && *pphead);assert(pos);SLTNode* pcur = *pphead;if(pos == *pphead){SLTPopFront(pphead);}else{while (pcur->next != pos){pcur = pcur->next;}pcur->next = pos->next;free(pos);pos = NULL;}
}

删除pos节点，我们需要先找到要删除节点的前一个节点，将前一个节点与后一个节点相连，再释放对应节点，对于删除头结点的情款，上诉逻辑也存在问题，我们调用头删来处理这一情况。

2.2.7在指定位置之后插入数据

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode*  newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;}

对于在指定位置之后插入数据，我们要先将newnode的next指向pos的下一节点，再将pos的next指向newnode,否则会出现无法找到原pos节点的下一节点的情况。这一函数没有需要特殊处理的函数。

2.2.8删除pos之后的节点

//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{assert(pos && pos->next);SLTNode* del = pos->next;//pos del del->nextpos->next = del->next;free(del);del = NULL;
}

对于删除pos之后的节点的，涉及的pos节点及之后两个节点都可以通过pos访问到，我们这里不需要创建其他节点，不过当我们将pos->next直接指向pos->next->next,我们会直接丢失pos之后节点的地址；如果我们直接释放pos->next，我们又会出现找不到pos之后第二个节点，因此，我们这里创建del记录pos->next的地址，将pos->next指向del的下一个节点，再将del释放。

2.2.9销毁链表

//销毁链表
void SListDesTroy(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while(pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}//pcur*pphead = NULL;
}

链表循环释放节点，最后将指向链表第一个有效节点的头结点置空。

注：感兴趣的读者可参照顺序表实现通讯录，实现基于数据结构-单链表的通讯录项目，笔者这里便不过多介绍。

//contact.h
#pragma once
#define NAME_MAX 100
#define SEX_MAX 4
#define TEL_MAX 11
#define ADDR_MAX 100//前置声明
typedef struct SListNode contact;//用户数据
typedef struct PersonInfo
{char name[NAME_MAX];char sex[SEX_MAX];int age;char tel[TEL_MAX];char addr[ADDR_MAX];
}PeoInfo;//初始化通讯录
void InitContact(contact** con);
//添加通讯录数据
void AddContact(contact** con);
//删除通讯录数据
void DelContact(contact** con);
//展示通讯录数据
void ShowContact(contact* con);
//查找通讯录数据
void FindContact(contact* con);
//修改通讯录数据
void ModifyContact(contact** con);
//销毁通讯录数据
void DestroyContact(contact** con);
//contact.c
#define _CRT_SECURE_NO_WARNINGS
#include"contact.h"
#include"SList.h"void LoadContact(contact** con) {FILE* pf = fopen("contact.txt", "rb");if (pf == NULL) {perror("fopen error!\n");return;}//循环读取文件数据PeoInfo info;while (fread(&info, sizeof(info), 1, pf)){SLTPushBack(con, info);}printf("历史数据导入通讯录成功！\n");
}void InitContact(contact** con) {LoadContact(con);
}void AddContact(contact** con) {PeoInfo info;printf("请输入姓名：\n");scanf("%s", &info.name);printf("请输入性别：\n");scanf("%s", &info.sex);printf("请输入年龄：\n");scanf("%d", &info.age);printf("请输入联系电话：\n");scanf("%s", &info.tel);printf("请输入地址：\n");scanf("%s", &info.addr);SLTPushBack(con, info);printf("插入成功！\n");}contact* FindByName(contact* con, char name[]) {contact* cur = con;while (cur){if (strcmp(cur->data.name, name) == 0) {return cur;}cur = cur->next;}return NULL;
}void DelContact(contact** con) {char name[NAME_MAX];printf("请输入要删除的用户姓名：\n");scanf("%s", name);contact* pos = FindByName(*con, name);if (pos == NULL) {printf("要删除的用户不存在，删除失败！\n");return;}SLTErase(con, pos);printf("删除成功！\n");
}void ShowContact(contact* con) {printf("%-10s %-4s %-4s %15s %-20s\n", "姓名", "性别", "年龄", "联系电话", "地址");contact* cur = con;while (cur){printf("%-10s %-4s %-4d %15s %-20s\n",cur->data.name,cur->data.sex,cur->data.age,cur->data.tel,cur->data.addr);cur = cur->next;}
}void FindContact(contact* con) {char name[NAME_MAX];printf("请输入要查找的用户姓名：\n");scanf("%s", name);contact* pos = FindByName(con, name);if (pos == NULL) {printf("要查找的用户不存在，查找失败！\n");return;}printf("查找成功！\n");printf("%-10s %-4s %-4d %15s %-20s\n",pos->data.name,pos->data.sex,pos->data.age,pos->data.tel,pos->data.addr);
}void ModifyContact(contact** con) {char name[NAME_MAX];printf("请输入要修改的用户名称:\n");scanf("%s", &name);contact* pos = FindByName(*con, name);if (pos == NULL) {printf("要查找的用户不存在，修改失败！\n");return;}printf("请输入要修改的姓名：\n");scanf("%s", pos->data.name);printf("请输入要修改的性别：\n");scanf("%s", pos->data.sex);printf("请输入要修改的年龄：\n");scanf("%d", &pos->data.age);printf("请输入要修改的联系电话：\n");scanf("%s", pos->data.tel);printf("请输入要修改的地址：\n");scanf("%s", pos->data.addr);printf("修改成功！\n");
}void SaveContact(contact* con) {FILE* pf = fopen("contact.txt", "wb");if (pf == NULL) {perror("fopen error!\n");return;}//将通讯录数据写入文件contact* cur = con;while (cur){fwrite(&(cur->data), sizeof(cur->data), 1, pf);cur = cur->next;}printf("通讯录数据保存成功！\n");
}void DestroyContact(contact** con) {SaveContact(*con);SListDesTroy(con);
}

三、链表OJ

3.1移除链表元素

思路一：

第一种思路是循环遍历原链表，将值为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 = NULL;ListNode* newTail = NULL;//遍历原链表ListNode* pcur = head;while(pcur != NULL){if(pcur->val != val){//链表为空if(newTail == NULL){newTail = newhead = pcur;}else{//链表不为空newTail->next = pcur;newTail = pcur;}}pcur = pcur->next;}if(newTail){newTail->next = NULL;}return newHead;
}

思路二：

第二种思路，我们反过来不去管值为val的节点，我们创建newHead、newtail两个节点用来管理一条新链表，newHead记录新链表第一个有效节点，方便后期返回，newTail记录当前的尾节点，方便尾插。我们在原链表中找值不为val的节点，并将这些节点一个一个尾插到这个新链表中，进行尾插过程中，我们还需要考虑到空链表尾插的问题，同时需要注意的是我们的尾插时通过节点内next的改变实现的，这就意味着如上图的5这个节点的next实际上还是指向6这个节点的。因此最后通过newtail->next = NULL，我们截断了新链表多余的尾巴。

此外对于原链表为空时的情况，循环直接结束，newTail指向NULL,为避免newtail->next = NULL出现问题，我们用if(newtail)处理，如果原链表为空直接返回newHead(NULL)。

3.2反转链表

思路一：

我们创建newHead、newTail指针管理新链表，循环遍历原链表，将原链表中节点运用头插的方式插入到新链表中，最后将尾节点的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 = NULL;ListNode* n2 = head;ListNode* n3 = head->next;while(n2 != NULL){n2->next = n1;n1 = n2;n2 = n3;if(n2 != NULL){n3 = n2->next;}}return n1;}

我们创建三个指针n1,n2,n3，n1初始赋值为NULL，n2赋值为第一个有效节点，n3指向n2的next，

循环遍历数组，我们将n2节点指向n1，然后n1移动到n2的位置，n2移动到n3,n3再移动到n2的next位置，循环重复接下来的操作，需要注意的是在这个过程中，当n2走到尾节点，并将当前节点反转完成后，n2走到空,我们不能继续 n3 = n2->next,因此，这个赋值操作，我们通过n2!=NULL处理一下，最后n2,n3走到空，n1正好走到原链表的尾节即反转后链表的第一个有效节点处。

此外，对于原链表出现链表为空的情况，我们直接直接返回。

3.3链表的中间结点

思路一：

循环遍历链表，count计节点个数，然后再循环遍历返回count/2的节点。

思路二：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {//创建快慢指针ListNode* fast = head;ListNode*slow = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}//此时slow刚好指向的就是中间节点return slow;
}

创建两个走的步速不同的指针，slow指针一次走一个节点，fast指针一次走两个节点，因为fast的步速是slow的两倍，当fast走完链表，slow恰好走完链表的一半。

需要注意的是while(fast && fast->next)中fast和fast->next不能调换顺序，因为如链表中有偶数个节点的情况下，fast最后一次会直接走到空,fast->next会执行错误；或者链表为空，fast->next会执行错误。

3.4合并两个有序链表

/*** 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) {if(list1 == NULL){return list2;}if(list2 == NULL){return list1;}ListNode* l1 = list1;ListNode* l2 = list2;//创建的新链表ListNode* newHead = NULL;ListNode* newTail = NULL;while(l1 && l2){if(l1->val <= l2->val){if(newTail == NULL){newHead = newTail = l1;}else{newTail->next = l1;newTail = newTail->next;}l1 = l1->next;}else{if(newTail == NULL){newHead = newTail = l2;}else{newTail->next = l2;newTail = newTail->next;}l2 = l2->next;}}//跳出循环有两种情况，要么l1走到空了，要么l2走到空了if(l1)newTail->next = l1;elsenewTail->next = l2;return newHead;
}

思路：

创建两个指针遍历原链表，比较两个指针指向的值，将值较小的节点尾插到新链表中，比较最后会出现l1先为空或者l2先为空，因此这里，我们需要进行判空处理，如果l1不为空，说明l2已经全部插入到新链表中，我们需要将l1剩余部分尾插到新链表中；如果l2先为空，那么就进行同样的处理。

原链表存在为空的情况，如果list1为空，list2为空或者不为空，我们返回list2；如果list2为空，那么同理。

优化：

写完代码后，我们发现在进行尾插时，当新链表为空时，l1、l2尾插都需要处理这一特殊情况，存在重复代码。

梳理重复代码的产生原因，我们发现是因为新链表存在空链表与非空链表两种情况。因此我们需要是链表不为空。解决的办法就是在新链表中插入一个头结点（哨兵位），这个头结点结构体的定义与其他节点一致，但是这个头结点不存储任何有效的数据，头结点的作用就是使链表不会存在为空链表的情况。需要注意的是头结点是哨兵位的特称，只有哨兵位可以成为头结点。

我们将包含头结点的链表称为带头链表。

插入头结点后，我们不需要再考虑空链表的情况，可以直接插入空链表。

3.5环形链表的约瑟夫问题

环形链表也称循环链表，一般链表的尾节点的next指针指向NULL，而环形链表的指针指向链表的第一个有效节点，这样通过尾节点，指针又回到链表的开始，逻辑上形成环状，可以循环访问的效果。

/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param n int整型 * @param m int整型 * @return int整型*/typedef struct ListNode ListNode;//创建节点ListNode* CreateNode(int i){ListNode* node = (ListNode*)malloc(sizeof(ListNode));node->val = i;node->next = NULL;return node;}//创建带环链表ListNode* CreateCircle(int n ){//先创建第一个节点ListNode* Head = CreateNode(1);ListNode* Tail = Head;for(int i = 2;i <= n;i++){Tail->next = CreateNode(i);Tail = Tail->next;}//首尾相连，链表成环Tail->next = Head;return Tail;}int ysf(int n, int m ) {//1.根据n创建带环链表ListNode* prev = CreateCircle(n);ListNode* pcur = prev->next;int count = 1;//当链表中只有一个节点的情况while(pcur->next != pcur){if(count == m){//销毁pcur节点prev->next = pcur->next;free(pcur);pcur = prev->next;count = 1;}else{//此时不需要销毁节点count++;prev = pcur;pcur = pcur->next;}}//先将值记录下来，再释放节点，节省资源int val = pcur->val;free(pcur);pcur = prev = NULL;return val;
}

思路：

题目本身并没有给我们提供成环链表，因此我们需要自己封装一个成环函数，这里因为我们需要第一有效节点的前一个节点，成环函数直接返回该节点。因为需要创建大量节点，我们再封装一个创建节点的函数。循环插入完节点，我们最后再将第一个有效节点与尾节点相连。

因为题目中会改变当前节点的前一个节点的指向，因此我们创建pcur和prev两个指针,我们创建count来计数。现假设有5个人，报到2的人，1到5按序连接，呈环状，prev指向5，pcur一开始指向1，count计1，prev不动，pcur移动到下一个节点，count计2，释放当前的2节点，prev指向的1节点next改为指向3节点，count重新计为1，重复循环上述过程，最后链表当中只剩下3这个节点，并且3这个节点自己指向自己。

我们根据count是否等于m来判断，如果等于，释放节点，节点释放完再将环断开的地方重新相连，如果不等，移动指针，count++.

最后pcur->next == pcur，节点自己指向自己，该节点即为我们所求的节点。

3.6分割链表

思路一：

在原链表上直接进行修改，创建pcur用于遍历,如果pcur节点的值小于x,pcur往后走，若pcur节点的值大于或等于x，尾插在原链表后，删除节点。不过，尾插前我们还需要创建ptail记录原链表的尾节点，用于循环结束的判断，此外还需要创建newPtail用于尾插。总的来说这种方法需要考虑的逻辑关系较为复杂。

思路二：

创建新链表，遍历原链表，若pcur节点的值小于x,头插在新链表；若pcur节点的值大于或等于x，尾插在新链表中。如果要优化代码，可以插入哨兵位，但是需要注意的是，哨兵位在链表中只能做头结点，因此进行头插时，节点插入在哨兵位之后，哨兵位始终是第一个。但是需要注意的是这样的思路调用头插和尾插，还要考虑哨兵位，需要考虑到逻辑关系较多。

思路三：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x){if(NULL == head){return head;}//创建两个带头链表ListNode* lessHead , *greaterHead , *lessTail , *greaterTail;lessHead = lessTail = (ListNode*)malloc(sizeof(ListNode));greaterHead = greaterTail = (ListNode*)malloc(sizeof(ListNode));//遍历原链表，将原链表中的节点尾插到大小链表中ListNode* pcur = head;while(pcur != NULL){if(pcur->val < x){//尾插到小链表中lessTail->next = pcur;lessTail = lessTail->next;}else{//尾插到大链表中greaterTail->next = pcur;greaterTail = greaterTail->next;}pcur = pcur->next;}//修改大链表的尾节点的next指针指向greaterTail->next = NULL;//若不加这一行，代码会出现死循环//小链表的尾节点和大链表的第一个有效节点首尾相连lessTail->next = greaterHead->next;free(greaterHead);greaterHead = NULL;return lessHead->next;
}

我们创建两个带头（哨兵位）链表，分为大小链表，将小于x的节点和大于等于x的节点分成了两堆，循环遍历原链表，如果节点值小于指定值x,我们就将节点尾插到lessHead和lessTail管理的链表中，否则尾插到greaterHead和greaterTail管理的链表中，最后将大小链表连接起来。对于特殊情况原链表为空的情况，我们直接返回head.

需要注意的是大链表的尾节点会充当新链表的尾节点，但是大链表尾节点在原有链表中不一定是尾节点，我们仅进行了尾插操作，因此对于大链表的尾节点我们需要手动置空，否则容易出现死循环问题。

lessTail->next = greaterHead->next和greaterTail->next = NULL;这两步操作不能反过来。因为当原链表内只有一个小于x的节点时，这是大链表内哨兵位next指向一个随机地址,大小链表相连，新链表尾节点指向随机地址，因此，我们需要greaterTail->n。ext = NULL，再lessTail->next = greaterHead->next。

将大链表通过尾插连接到上到小链表的尾节点，一定是lessTail->next = greaterHead->next，因为greaterHead指向哨兵位，哨兵位本身并不存储任何有效值，同理返回大小链表合并后的新链表，我们直接返回lessHead->next。

四、链表的分类

链表的结构非常多样，以下情况组合起来就有8种（2 x 2 x 2）链表结构：

4.1链表说明

单向：每个节点中仅存有指向下一个节点的指针，这个链表只能单向遍历。

双向：每个节点中存有指向前一个节点的指针和指向后一个节点的指针，通过前驱指针，双线链表比起单向链表可以实现双向遍历。

带头：指链表中哨兵位节点，该哨兵位节点即头结点，链表中的头结点特指哨兵位，哨兵位节点不存储任何有效元素，只是站在这里“放哨的”，避免遍历循环链表出现死循环。

不循环：尾节点指向NULL,链表逻辑上成线性。

循环：尾节点指向链表第一个节点，逻辑上链表呈环状（如果只有一个节点依然要满足这个条件，通过自己指向自己来实现）。

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：单链表和双向带头循环链表

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结
构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都
是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带
来很多优势，实现反而简单了，后面我们代码实现了就知道了。

五、双向链表

5.1双向链表的实现

5.1.1.节点的定义

typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* next; //指针保存下一个节点的地址
struct ListNode* prev; //指针保存前一个节点的地址
LTDataType data;
}LTNode;

双向链表节点的结构体内，除了保存的值外，还有指向下一个节点的指针以及指向前一个节点的指针，这样双向链表可以既可以向前也可以向后访问。

5.1.2链表打印

//打印
void LTPrint(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while(pcur != phead){printf("%d->",pcur->data);pcur = pcur->next;}puts("NULL");
}

因为双向链表逻辑上成环状，当pcur从头结点出发，遍历一遍还会回到头结点。因此循环结束条件是pcur != phead。

5.1.3申请节点与初始化

//申请节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* node = (LTNode*)calloc(1,sizeof(LTNode));if (NULL == node){perror("calloc failed!");exit(1);}node->data = x;node->next = node->prev = node;return node;
}
//初始化
void LTInit(LTNode** pphead)
{assert(pphead);*pphead = LTBuyNode(-1);
}
//LTNode* LTInit()
//{
//
//	LTNode*phead = LTBuyNode(-1);
//	return phead;
//}

双向链表是带头链表，根据定义，链表中必须有头结点，头结点不存储有效的数据，当链表只有头结点时，链表即为空链表。对于只有哨兵位的链表，我们不能将哨兵位的next指针和prev指针初始化为NULL，这时候链表是不循环的，不符合双向链表的定义。正确的做法是，我们要将链表循环起来，对于只有头结点的链表，可以让节点自己指向自己。

双向链表初始化是为头指针创建头结点（插入数据之前后删除数据之后链表中必须有一个头结点），因为头结点不存储有效的数据，调用LTBuyNode函数可以随便赋予一个值。

初始化思路既可以改变原有的头指针让它指向头结点，也可以将指向头结点的头指针返回返回。

5.1.4尾插

因为双线链表中初始化后无论何时，都必须有头结点，头结点不能被删除，地址不能被改变。因此插入或删除节点时，我们不需要对头指针进行操作。函数参数传递一级指针即可。

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;}

尾插前assert(phead)，确保链表包含头结点。进行尾插操作时，为了不造成意外的错误，我们先改变newnode,prev指向原链表的尾节点d3（phead->prev），next指向头结点head。然后将d3的next指向newnode,head的prev指向newnode。

5.1.5头插

//前插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;}

头插根据定义只能插到头结点的后面，，如果插到头结点前面就是尾插（循环链表可以看成环状，头结点可视作定义头尾的标志。）

头插先改变newnode的prev指针和next指针指向，然后再改变d1和head指针指向。

phead->next->prev = newnode和phead->next = newnode;这两行链表不能调换，如果调换phead->next指向newnode,不再指向d1，如果要调换那么需要将phead->next改为newhead->next。

5.1.6尾删

//尾删
void LTPopBack(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = phead = NULL;}

尾删操作前要先确保链表有效且链表不能为空（只有一个哨兵位）。尾删时，我们先修改head和d2指针的指向，最后再释放d3节点，在这个过程中我们发现为了调用d2节点，要先调用d3节点，导致会出现phead->prev->prev->prev这样复杂的情况，同时为了确保d3节点不丢失，我们直接用del专门存放d3的地址（phead->prev）。之后我们改变对应指针就可以了。

5.1.7头删

//前删
void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->next;phead->next = del->next;del->next->prev = phead;free(del);del = phead = NULL;
}

同尾删一样，头结点不可改变，只能对头结点之后的节点进行操作，我们这里还将创建指针专门存放d1的地址。之后改变相应指针即可。

5.1.8查找节点

//查找节点
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* pcur = phead->next;while(pcur != phead){if(x == pcur->data){return pcur;}pcur = pcur->next;}return NULL;
}

循环挨个比较。

5.1.9在指定位置之后插入数据

//在指定位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}

通过LTFind函数，找到对应数值节点的地址，再将地址传入LTInsert中，插入之前确保插入节点有效，然后根改变对应指针（代码与头插相似，双向链表成环，实质一样，插入位置不同。）

5.1.10删除指定节点

//指定位置删除
void LTErase(LTNode* pos)
{assert(pos && pos->next != pos);pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}

通过LTFind函数，找到对应数值节点的地址，再将地址传入LTInsert中，插入之前确保插入节点有效，然后根改变对应指针.需要注意的是虽然这里我们删除节点，会对实参造成影响，但是我们之前的函数形参普遍传的一级指针，为了不增加我们封装这一套方法的记忆使用成本，参数这里我们传一级指针（保持接口的一致性），函数结束，手动将实参plist置空（成本相对较小，如果不在使用plist指针，不置空也可以）。

5.1.11判空

//判断是否双向链表是否为空
bool LTEmpty(LTNode* phead)
{assert(phead);if(phead->next == phead){return true;}return false;
}

双向链表为空，头结点（哨兵位）自己指向自己。

5.1.12销毁节点

//销毁
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* ret = pcur->next;free(pcur);pcur = ret;}free(pcur);pcur = phead = NULL;}

循环遍历释放，先记录下一个节点，再释放当前节点。

与指定位置删除类似，为了保持接口一致，降低使用成本，形参传入一级指针。