数据结构--单链表

概念与结构

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

用火车来形如链表比较贴切，每节车厢代表着链表的每一个节点，每个节点之间又相互连接。

结点

与顺序表不同的是，链表里的每节"车厢"都是独立申请（为动态申请，不需要占用空间，所以空间复杂度始终为O（1），这也是链表的一个优点。）下来的空间，我们称之为“结点/结点”。结点的组成主要有两个部分：当前结点要保存的数据和保存下⼀个结点的地址（指针变量）。图中指针变量plist保存的是第⼀个结点的地址，我们称plist此时“指向”第⼀个结点，如果我们希望plist“指向”第⼆个结点时，只需要修改plist保存的内容为0x0012FFA0。链表中每个结点都是独立申请的（即需要插⼊数据时才去申请⼀块结点的空间），我们需要通过指针变量来保存下⼀个结点位置才能从当前结点找到下⼀个结点。

链表的性质

1、链式机构在逻辑上是连续的，在物理结构上不⼀定连续
2、结点⼀般是从堆上申请的
3、从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续
结合前⾯学到的结构体知识，我们可以给出每个结点对应的结构体代码：
假设当前保存的结点为整型：
struct SListNode
{
int data; //结点数据
struct SListNode* next; //指针变量⽤保存下⼀个结点的地址
};
当我们想要保存⼀个整型数据时，实际是向操作系统申请了⼀块内存，这个内存不仅要保存整型数据，也需要保存下⼀个结点的地址（当下⼀个结点为空时保存的地址为空）。
当我们想要从第⼀个结点⾛到最后⼀个结点时，只需要在当前结点拿上下⼀个结点的地址就可以了。
因此我们可以看出：链表的存储数据时单向的，可以从头结点查到尾结点，却无法从尾结点到头节点，这是相对于顺序表的缺点。

链表的打印

只需要给头指针即可，令图中的pcur指针每次循环指向其所指向的下一个节点，循环结束的判断条件是当pcur所指为空指针时，循环结束，证明链表遍历完成。

实现单链表

头文件，相当于所有实现函数的目录。

SList.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* phead, SLTDataType x);
//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDestroy(SLTNode** pphead);

list.c文件，用于对每个功能的函数的实现。

#include"list.h"
#include<assert.h>
#include<string.h>
SListNode* BuySListNode(SLTDateType x)//动态申请第一个节点
{SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));assert(newnode);newnode->data = x;newnode->next = NULL;return newnode;
}
void SListPrint(SListNode* plist)//单链表的打印
{SListNode* pcur = plist;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}
void SListPushBack(SListNode** pplist, SLTDateType x)//单链表的尾插
{assert(pplist);if (*pplist == NULL){*pplist=BuySListNode(x);}else{SListNode* pcur = *pplist;while (pcur->next){pcur = pcur->next;}pcur->next= BuySListNode(x);}
}
void SListPushFront(SListNode** pplist, SLTDateType x)//单链表的头插
{assert(pplist);SListNode* pcur = BuySListNode(x);pcur->next = *pplist;*pplist = pcur;
}
void SListPopBack(SListNode** pplist)//单链表的尾删
{assert(pplist && *pplist);if ((*pplist)->next == NULL){free(*pplist);*pplist = NULL;}else{SListNode* pcur = *pplist;SListNode* ppcr = *pplist;while (pcur->next){ppcr = pcur;pcur = pcur->next;}ppcr->next = NULL;free(pcur);}
}
void SListPopFront(SListNode** pplist)//头删
{assert(pplist && *pplist);if ((*pplist)->next == NULL){free(*pplist);*pplist == NULL;}else{SListNode* pcur = *pplist;pcur = (*pplist)->next;free(*pplist);*pplist = pcur;}
}
SListNode* SListFind(SListNode* plist, SLTDateType x)//查找
{assert(plist);SListNode* pcur = plist;while (pcur->data != x){pcur = pcur->next;}return pcur;
}
void SListInsertAfter(SListNode* pos, SLTDateType x)// 单链表在pos位置之后插入x
{assert(pos);SListNode*pcur=BuySListNode(x);SListNode* lis = pos->next;pos->next = pcur;pcur->next = lis;
}
void SListEraseAfter(SListNode* pos)// 单链表删除pos位置之后的值
{assert(pos);if (pos->next == NULL){perror("删除失败");}else{SListNode* pcur = pos->next->next;free(pos->next);pos->next = pcur;}
}
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x)// 在pos的前面插入
{assert(pphead && pos && *pphead);if (pos == *pphead){SListNode* pcur=BuySListNode(x);pcur->next = *pphead;*pphead = pcur;}else{SListNode* pcur = *pphead;while (pcur->next != pos){pcur = pcur->next;}SListNode* plist=BuySListNode(x);pcur->next = plist;plist->next = pos;}
}
void SLTErase(SListNode** pphead, SListNode* pos)// 删除pos位置
{assert(pphead && pos && *pphead);if (pos == *pphead){free(*pphead);*pphead == NULL;}else{SListNode* pcur = *pphead;while (pcur->next != pos){pcur = pcur->next;}pcur->next = pos->next;free(pos);pos == NULL;}
}
void SLTDestroy(SListNode** pphead)//删除链表；
{assert(*pphead && pphead);SListNode* pcur = *pphead;while (pcur){SListNode* next = pcur->next;free(pcur);pcur = next;}*pphead == NULL;
}

链表的分类

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


虽然有这么多的链表的结构，但是我们实际中最常⽤还是两种结构：单链表和双向带头循环链表
1.⽆头单向⾮循环链表：结构简单，⼀般不会单独用来存数据。实际中更多是作为其他数据结构的⼦
结构，如哈希桶、图的邻接表等等。另外这种结构在笔试⾯试中出现很多。
2.带头双向循环链表：结构最复杂，⼀般用在单独存储数据。实际中使用的链表数据结构，都是带头
双向循环链表。另外这个结构虽然结构复杂，但是使⽤代码实现以后会发现结构会带来很多优势，实
现反⽽简单了，后⾯我们代码实现了就知道了。

单链表算法题之环形链表

环形链表一

来自力扣的算法题：
链接: https://leetcode.cn/problems/linked-list-cycle/description/

对于环形链表，快慢指针必不可少，由于快指针要比慢指针遍历的更快，我们可以假设当慢指针刚到环的第一个位置时，快指针与慢指针的差距为N，而环的总长度为C，链表的头节点到环的第一个结点的距离为L，

此时我们假设快指针走三步，慢指针走一步，所以快指针与慢指针的相对速度为3-1步，如果N为偶数，那么随着快指针的遍历，N每次会减2，直到0，此时快慢指针重合，然后返回。如果N为奇数，那么N的值最后就会由1变为-1，这是说明快指针赶上并超过了慢指针，并没有重合，为了验证下一圈是否会重合，我们这样计算：在慢指针刚进入环时，慢指针走的路程为L，快指针为3L，等于L+C-N+kC（kC的意思是快指针走了k圈环后来到此位置），列出等式：3L=L+C-N+kC；化简：2L=（k+1)C-N;2L一定为偶数，则C-N必须为偶数才符合等式，情况只有两种：C奇数N奇数，C偶数N偶数。N为偶数在一定相遇，不考虑此种情况。N为奇数时，当快指针超过慢指针来到下一圈，此时距离为C-1；前面提到C必需为奇数，那么C-1为偶数，所以必定相遇。

环形链表二

链接: https://leetcode.cn/problems/linked-list-cycle-ii/description/

大致的一个思路是：仍然使用快慢指针，记录快慢指针相遇的节点，对结点和头节点同时遍历直到指向同一个地址时，此地址为环的起始点。
推理：

我们所要推理的是：L=C-N。首先让慢指针每次走一步，快指针每次走两步，在相遇点时慢指针走了L+N步，快指针走了L+N+kC步，等于2L+2N步，带入等式：L+N+kC=2L+2N;化简后可得：（k-1）C+C-N=L;其中（k-1)C为快指针走的圈数，加上后对位置没有任何影响，所以在判断时可以省去，为C-N=L；由此可以得出在相遇的位置到环的起始点的距离与头节点到环的起始点的位置相等。