前言
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。链表的形式有很多，本篇文章主要介绍的是单链表且无头结点。在严版数据结构（C语言 第2版）中，单链表采用的是有头节点，这两种形式，各有利弊。含头节点的单链表在学习时，可能会容易些，但是在实践中或者在力扣中做题时，很少会有带头节点。但是有时候做题，使用带头节点的单链表会简单许多，不常见。
概述
一个结点有两个部分组成，数据域（val），指针域（next）。
链表的实现
初始化
在无头单项非循环链表中，需要声明一个数据域和指针域，指针域指向的是下一个节点的地址，数据域是当前节点的数据。这里需要注意的是，在声明指针域是，因为是结构体指针类型，所以一定要写全了。
typedef int SLNDataType;
//初始化
typedef struct SListNode
{
SLNDataType val; //指针域
struct SListNode* next; //指针域
}SLNode;
遍历单链表
遍历单链表，就是从单链表的第一个节点一直访问到单链表的最后一个节点。
形参接收到的是单链表的第一节点，然后需要用指针去维护节点。通过改变指针的指向，从而实现访问不同的节点。
当cue不为空指针时，继续访问下一个节点，操作为：==cur=cur->next==
当cur为空时，已经访问结束，无需继续遍历。
需要注意的是，这里的判断条件是cur为不为空，而不是cur->next为不为空，如果去判断cur->next，那么当cur->next==NULL时，访问的是最后一个节点为空，此时还没有遍历结束。
void SLTprintf(SLNode* phead)
{
SLNode* cur = phead;
while (cur)
{
printf("%d->", cur->val);
cur = cur->next;
}
printf("NULL\n");
}
创建新节点
用malloc函数，在堆上申请一片空间来存储数据，当newcode为空时，表示开辟失败。
//创建新节点
SLNode* CreateNode(SLNDataType x)
{
SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->val = x;
newnode->next = NULL;
return newnode;
}
尾插
尾插又称后插法，顾名思义，是将新节点逐个插入链表的尾部来创建链表。每次申请一个新节点，读入相应的数据元素值，同时需要一个尾指针指针链表的尾节点（tail）。
需要注意的是，当链表为空时，直接将新创建的节点当作第一个节点。尾插是封装在函数里实现的，对于函数来说，形参的改变不会改变形参，因此需要传递地址，即址传递，因此需要一个二级指针接收。
pphead是头指针（plist）的地址，*pphead是对它进行解引用。
void SLTPushBack(SLNode** pphead, SLNDataType x)
{
SLNode* newnode = CreateNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
// 找尾
SLNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
空链表和链表不存在的区别：
- 空链表： 头指针为空，也就是plist==NULL表示是一个空链表
在遍历、尾插、头插时允许空链表存在，在头删、尾删中不允许出现 - 链表不存在： ppead==NULL，表示链表不存在，这种情况不允许存在的，因此，每次都需检查一下链表存不存在。
头插
头插法即前插法，逐个将新节点插入到链表的头部来创建，每次申请一个新节点，读入相应的数据元素值。传递的也是二级指针，将新节点的头节点给newnode->next，将newhead变成头节点。
//头插
void SLTPushFront(SLNode** pphead, SLNDataType x)
{
SLNode* newnode = CreateNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
尾删
尾删是将最后一个节点给释放掉，同时还需要保存倒数第二个节点，将它的指针域存放的地址改成NULL。需要两个指针，一个找尾，一个找倒数第二个节点，同时遍历。
空链表不能删，链表中只有一个节点的链表删除后会变成一个空链表，改变头指针需要存放地址，形参也是一个二级指针。
void SLTPopBack(SLNode** pphead)
{
assert(*pphead);
assert(pphead);
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLNode* tail = *pphead;
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
头删
头删需要改变的是头指针的地址，因此传的也是地址。tous需要考虑链表是否为空，如果是空链表就不能操作了，因此需要先断言。在删除头节点的时候，需要先保存一下头节点，否则释放了头节点，就找不到原来的头节点了。
//头删
void SLTPopFront(SLNode** pphead)
{
assert(pphead);
assert(*pphead);
SLNode* tmp = *pphead;
*pphead = (*pphead)->next;
free(tmp);
}
单链表的查找
单链表的查找实际上就是遍历单链表，遍历过程中，找到你所需要的数值，如果是的，就返回当前节点，不是就继续往下遍历，直到链表为空。如果遍历完了还没有找到，那就说明你想查找的数值不在链表里面，返回空指针。
SLNode* SLTFind(SLNode* phead, SLNDataType x)
{
SLNode* ptr = phead;
while (ptr)
{
if (ptr->val == x)
{
return ptr;
}
else
{
ptr = ptr->next;
}
}
return NULL;
}
在pos位置之前插入一个节点
遍历链表，找到pos之前的节点，然后按照尾插的方式插入即可。但是需要判断一种情况，如果pos就是第一个节点，那么在pos位置之前插入，那就相当于是头插了。有限制条件，pos一定是链表中的一个有效节点。
//在pos位置之前插入
SLNode* SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{
assert(pphead);
assert(*pphead);
assert(pos);
//pos如果为头节点，就是头插
if (*pphead == pos)
{
SLTPushFront(pphead, x);
}
//pos不是头节点
else
{
SLNode* pre = *pphead;
while (pre->next != pos)
{
pre = pre->next;
}
SLNode* newnode = CreateNode(x);
pre->next = newnode;
newnode->next = pos;
}
}
在pos位置删除节点
pos需要是链表中存在的节点，链表不能为空。pos可能是头节点，因此需要二级指针，这种情况就相当于头删。删除pos节点时，需要一个指针保存pos前一个节点，让pos前一个结点的指针域直接指向pos下一个节点即可，释放pos，让pos=NULL。
//在pos位置删除节点
void SLTErase(SLNode** pphead, SLNode* pos)
{
assert(pphead);
assert(*pphead);
assert(pos);
if (*pphead == pos)
{
SLTPopFront(pphead);
}
else
{
SLNode* pre = *pphead;
while (pre->next != pos)
{
pre=pre->next;
}
pre->next = pos->next;
free(pos);
pos = NULL;
}
}
在pos位置后插入节点
需要保证pos是链表的一个有效节点，然后让新节点的指针域指向pos的下一个节点，然后让pos的指针域指向新节点。
//pos位置之后插入
void SLTInsertAfter(SLNode* pos, SLNDataType x)
{
assert(pos);
SLNode* newnode = CreateNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
删除pos后一个节点
删除pos后一个节点，pos已经是一个节点，因此，链表不可能为空。
需要注意的是，这里不能直接是pos的指针域指向pos后的第二个节点，因为每一个节点都是通过malloc在堆上申请的，不使用的时候要主动的去释放掉，也就是free掉，把这块空间归还给操作系统，否则会导致内存泄漏。需要借助一个节点，保存待删节点，然后去释放借助的这一个节点并置为空指针即可。
//删除pos后一个节点
void SLTEraseAfter(SLNode* pos)
{
assert(pos);
assert(pos->next);
SLNode* tmp = pos->next;
pos->next = pos->next->next;
free(tmp);
tmp = NULL;
}
销毁
void SLTDestroy(SLNode** pphead){
assert(pphead);
SLNode* cur = *pphead;
while (cur)
{
SLNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
结尾
单链表相对于顺序表会难很多，也会有很多的坑点，我们要去判断链表是否为空？（在遍历、尾插、头插时允许空链表存在），头节点是否存在？什么时候传二级指针？
