单链表
这张图是我们待会要实现的功能，我会尽可能的将每一步都说的很详细，方便理解。
物理存储结构上非连续
、非顺序的存储结构，数据元素的
逻辑顺序
是通过链表中的
指针链
接
次序实现的 。
1的位置是当前链表的起始位置，我们称之为表头，它里面放着的是第一个数据的地址（2），而2里面不仅有数据还有p2，p2指向的是第二个数据的位置，第二个数据里面不仅有2，同时里面放着p3，p3指向下一个数据的位置，而4这里最后的指针指向的是NULL，也就是说链表就到这里结束。
就像一条火车，里面的数据就是我们的车厢，而指针就是将数据链接起来的链条，所以我们称之为链表。
我们如何实现链表？
跟顺序表一样，我们要用到跟顺序表（我的专栏也写过结构体）类似的结构体，但是我们顺序表里面是这么写的：
我们拿一个指针指向一块连续的空间，然后有一个size记录当前有效数据，capicity记录容量，这样好处是我们可以通过下标来访问其中每一个数据，但缺点是当我们开辟数组的时候，第一个数组容量可能是10，然后我们放11个元素进去，这个时候空间不够，我们就重新开辟空间，一般我们开辟空间都是直接将原空间翻倍，但这里20个空间只放11个元素，空间就有些浪费了。
那我们链表是怎么写的呢？
同样，我们先来一个结构体，data就是我们除非囊的数据，而第二个参数是next，也就是下一个结构体的地址，当我们需要放11个数据的时候，顺序表我们可能直接创建了一整块数组然后往里面放，但链表则是一次放一个数据到里面，然后根据需求再开辟一空间放下一个数据。
尾插
因为打印需要先有内容，所以我们先冲尾插开始写：
尾插还没写完，我们就发现一个问题，就是当我们每次插入的时候都需要开辟一块空间，但开辟空间的代码又比较长，每次写起来会很麻烦，所以我们可以将其封装为一个函数 ：
SListNode* BuySLisenode(SLTDateType x)
{
SListNode*newnode = (SListNode*)malloc(sizeof(SListNode));
if (newnode == NULL)
{
printf("malloc fail\n");
}
else
{
newnode->data = x;
newnode->next = NULL;
}
return newnode;
}我们拿到要插入的数据，先计算空间大小，然后进行判断，如果指针为空指针我们就打印开括失败，如果成功，我们就将数据放到新开括空间的里面，然后将其下一个指针指向空，并返回这个这一块空间的地址。
然后我们直接调用这个函数即可，尾插我们看代码分析：
void SListPushBack(SListNode** pphead, SLTDateType x)
{
SListNode* newnode = BuySLisenode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SListNode*cur=*pphead;
while (cur->next != NULL)
{
cur = cur->next;
}
cur->next = newnode;
}
}尾插分两种情况，第一种，目前什么都没有，我们直接将新创建好的结构体地址给原本指针即可。
第二种，是目前里面已经有了结构体，我们就得找到数组的最后一个结构体，而最后的一个结构体它的指针肯定为空，然后将这个结构体的指针指向变成我们新创建的结构体地址。
为了看效果，我们再写一个打印函数，这个函数实现也很简单，我们进行判断，如果结构体指针不为空，我们就打印里面的内容，如果为空我们就停下：
头插
既然实现了尾插，那我们再实现一个头插，相较于顺序表的头插还要移动数据，链表就简单一点看图：
原本我的1指向2，现在我中间插入一个5，我只需要将1指向的位置变成5，然后5的指针指向2即可：
看代码：
void SListPushFront(SListNode** pphead, SLTDateType x)
{
SListNode* newnode = BuySLisenode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
newnode->next = *pphead;
*pphead = newnode;
}
}同样，我们先创建一个新的结构体，然后给它赋值，随后我们还是先判断当前链表有没有数据，没有就直接赋值，如果有，那就将我们新创建的结构体的下一个地址赋值为之前的第一个数据的地址，也就是我们传进来的那个地址解引用，然后我们再将原本的指向第一个元素的地址指向我们新创建的节点。
实现效果如下：
指定位置插入
然后我们来一个难一点的，在指定位置插入，这里说难一点是因为我们要先找到指定的位置，然后再插入数据，但如果熟练适用以上两个插入，那这里其实也没那么难：
我原本是这样的结构，我现在要在2的位置插入一个结构，是不是要先找到2数据的位置，然后将它原本指向3的地址赋给我的新节点，然后将新节点的地址给它：
然后我们就可以开始写代码了：
void SeqListInsert(SListNode** pphead, size_t pos, SLTDateType x)
{
SListNode* newnode = BuySLisenode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SListNode*cur = *pphead;
while (pos--)
{
if (cur == NULL)
{
printf("位置错误\n");
}
else
{
cur = cur->next;
}
}
newnode->next = cur->next;
cur->next = newnode;
}
}这里是拿while循环来找的位置，实现的效果是这样的：
——————
解决了插入，那我们来解决一下删除
尾删
尾删就是将倒数第二个结构体的指针置为空指针
我们直接进行判断语句即可：
void SListPopBack(SListNode** pphead)
{
if (*pphead == NULL)
{
printf("链表为空\n");
}
SListNode*cur = (*pphead)->next;
SListNode*perv = *pphead;
if (cur == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
while (cur->next)
{
if (cur->next != NULL)
{
cur = cur->next;
perv = perv->next;
}
}
perv->next = NULL;
free(cur);
}
}同样，一进来我们先判断传进来的地址是否有内容，如果没有内容我们就可以直接打印链表为空，随后我们拿两个指针，第一个从第二个结构体开始，第二个从起始位置，因为我们要靠第一个来判断结构体指针是否为空，如果结构体不为空，我们就让第一个和第二个分别指向下一个结构体，如果第一个结构体走到指针为空的结构体，那第二个正好是它的前一个，我们将第二个的指针置为空，然后释放第一个指针的位置即可，演示效果：
头删
头删说来也很简单，原本传进来的地址放着的是第一个结构体的地址，我们可以直接将第二个结构体的位置传给起始地址即可：
代码实现如下：
void SListPopFront(SListNode** pphead)
{
if (*pphead == NULL)
{
printf("链表为空\n");
}
else
{
SListNode*cur = (*pphead)->next;
free(*pphead);
*pphead = cur;
}
}我们直接拿到第二个结构体的地址，然后销毁第一个结构体，随后将地址重新赋值即可，看效果：
删除指定位置的值
这个实现其实就是一个复合，我们先找到位置，这里可以参考指定位置插入，然后删除结构体，删除我们也可以参考尾删，我们将其结合：
void SListEraseAfter(SListNode**pphead, size_t pos)
{
if (*pphead == NULL)
{
printf("链表为空\n");
}
SListNode*cur = *pphead;
if (pos)
{
while (pos--)
{
if (cur->next == NULL)
{
printf("位置错误\n");
}
else
{
cur = cur->next;
}
}
SListNode*nex = cur->next;
cur->next = nex->next;
free(nex);
}
else
{
*pphead = (*pphead)->next;
free(cur);
}
}同样，一进来我们就可以判断是否为空指针，如果为空我们打印错误，如果不为空，我们就创建一个结构体变量来帮助我们找指定位置的数据，找到了数据之后我们在删除之前要先借助它找到它之后结构体的地址，所以我们才有
SListNode*nex = cur->next;
cur->next = nex->next;
free(nex);因为一旦你先删除，那这之后的所有结构体就再也找不到了，一定要先留下地址，再删除。
如果要删除0地址，那我们直接将第二个结构体的地址给地起始地址即可，别忘了释放创建的临时结构体。
查找
查找可能是最简单的，我们直接遍历，如果找到了数据我们就返回，没找到就返回-1，看代码：
SListNode* SListFind(SListNode* phead, SLTDateType x)
{
if (phead == NULL)
{
printf("空链表\n");
}
SListNode* cur = phead;
while (cur != NULL)
{
if (cur->data == x)
{
return cur;
}
else
{
cur = cur->next;
}
}
return -1;
}销毁
void SListDestory(SListNode* phead)
{
SListNode*cur = phead;
SListNode*nex = phead;
while (cur)
{
cur = cur->next;
free(nex);
nex = cur;
}
}我们先创建两个结构体，第一个指向第二个数据，第二个指向第一个数据，我们先删除第一个数据，然后将第一个的值赋给第二个，再销毁第二个，循环到最后为空指针就可以结束了。
——————-
这里放上所有代码，有需要可以直接复制：
SList.h
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#define SLTDateType int
typedef struct SListNode
{
int data;
struct SListNode* next;
} SListNode;
void SListPrint(SListNode* phead); //打印
void SListPushBack(SListNode** pphead, SLTDateType x); //尾插
void SListPushFront(SListNode** pphead, SLTDateType x); //头插
void SeqListInsert(SListNode** psl, size_t pos, SLTDateType x);//在指定位置插入
void SListPopBack(SListNode** pphead);// 单链表的尾删
void SListPopFront(SListNode** pphead);// 单链表头删
void SListEraseAfter(SListNode**pphead, size_t pos);//删除pos之后的值
SListNode* SListFind(SListNode* phead, SLTDateType x);//单链表的查找
void SListDestory(SListNode* phead);//销毁链表
SList.c
#include"SList.h"
void SListPrint(SListNode* plist)
{
if (plist == NULL)
{
printf("单链表已空!\n");
return;
}
SListNode*cur = plist;
while (cur)
{
printf("%d -> ", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
SListNode* BuySLisenode(SLTDateType x)
{
SListNode*newnode = (SListNode*)malloc(sizeof(SListNode));
if (newnode == NULL)
{
printf("malloc fail\n");
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void SListPushBack(SListNode** pphead, SLTDateType x)
{
SLTDateType* newnode = BuySLisenode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SListNode*cur = *pphead;
while (cur->next)
{
cur = cur->next;
}
cur->next = newnode;
}
}
void SListPushFront(SListNode** pphead, SLTDateType x)
{
SListNode* newnode = BuySLisenode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
newnode->next = *pphead;
*pphead = newnode;
}
}
void SeqListInsert(SListNode** pphead, size_t pos, SLTDateType x)
{
SListNode* newnode = BuySLisenode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SListNode*cur = *pphead;
while (pos--)
{
if (cur == NULL)
{
printf("位置错误\n");
}
else
{
cur = cur->next;
}
}
newnode->next = cur->next;
cur->next = newnode;
}
}
void SListPopBack(SListNode** pphead)
{
if (*pphead == NULL)
{
printf("链表为空\n");
}
SListNode*cur = (*pphead)->next;
SListNode*perv = *pphead;
if (cur == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
while (cur->next)
{
if (cur->next != NULL)
{
cur = cur->next;
perv = perv->next;
}
}
perv->next = NULL;
free(cur);
}
}
void SListPopFront(SListNode** pphead)
{
if (*pphead == NULL)
{
printf("链表为空\n");
}
else
{
SListNode*cur = (*pphead)->next;
free(*pphead);
*pphead = cur;
}
}
void SListEraseAfter(SListNode**pphead, size_t pos)
{
if (*pphead == NULL)
{
printf("链表为空\n");
}
SListNode*cur = *pphead;
if (pos)
{
while (pos--)
{
if (cur->next == NULL)
{
printf("位置错误\n");
}
else
{
cur = cur->next;
}
}
SListNode*nex = cur->next;
cur->next = nex->next;
free(nex);
}
else
{
*pphead = (*pphead)->next;
free(cur);
}
}
SListNode* SListFind(SListNode* phead, SLTDateType x)
{
if (phead == NULL)
{
printf("空链表\n");
}
SListNode* cur = phead;
while (cur != NULL)
{
if (cur->data == x)
{
return cur;
}
else
{
cur = cur->next;
}
}
return -1;
}
void SListDestory(SListNode* phead)
{
SListNode*cur = phead;
SListNode*nex = phead;
while (cur)
{
cur = cur->next;
free(nex);
nex = cur;
}
}主函数我就不放了，因为操作函数都在上面，也需要直接调用即可。
———–
修改
更新，多一个修改函数，能将指定位置的值修改，原理就是找到位置然后修改，原理没变：
void SListrevise(SListNode* phead, size_t pos, int x)
{
if (phead == NULL)
{
printf("链表为空\n");
}
else
{
SListNode*cur = phead;
while (--pos)
{
if (cur == NULL)
{
printf("位置错误\n");
}
else
{
cur = cur->next;
}
}
cur->data = x;
}
}演示效果：
如果是pos–，那就会先运行一次再修改，也就是说位置会不一样，这里看图：
这里是pos–，可以看到修改的是第二个值
同样的代码，这里是–pos，修改的是第一个值，注意一下就好
————-
带头双向循环链表
1、如何开辟新的节点和初始化链表
2、双向链表的打印
3、双向链表尾插
4、双向链表尾删
5、双向链表头插
6、双向链表头删
7、双向链表查找
8、双向链表在pos的前面进行插入
9、双向链表删除pos位置的节点
10、双向链表的销毁
——–
事前准备：
我们需要一个创建一个结构体类型，并将里面的一些类型重定义名字，如下：
typedef int LTDataType;
typedef struct ListNode
{
LTDataType _data;
struct ListNode* next;
struct ListNode* prev;
}ListNode;我们还要知道双向带头循环链表是什么样的：
———
如何开辟新的节点和初始化链表
我们知道，在链表中尾插，或者头插，你都必须先创建一个结构体，因为是双向带头循环的链表，所以这个链表必须有以下几条：
1、我们存放的内容
2、下一个结构体的地址
3、上一个结构体的地址
4、如果链表仅有表头，那么表头的下一个元素和上一个元素必须指向自己
了解了条件，我们就来初始化我们链表：
void ListInit(ListNode** pphead)
{
assert(pphead);
*pphead = BuyLTNode(0);
(*pphead)->next = *pphead;
(*pphead)->prev = *pphead;
}———–
然后我们来看看如何创建新的节点：
跟单链表一样，我们开辟一块空间，将里面的值改成我们需要插入的值，然后再将其指针置为NULL，返回即可：
ListNode* BuyListNode(int x)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
if (newnode == NULL)
{
printf("malloc false\n");
exit(-1);
}
newnode->_data = x;
newnode->prev = NULL;
newnode->next = NULL;
return newnode;
}————
但是问题来，在初始化函数的时候，我们需不需要传入二级指针呢？
在单向不循环的链表时，我们是传入的链表的地址，因为如果我们要头插或者尾插，有可能会改变我们链表的表头位置
比方说：
ListNode* list = NULL;
尾插;
如果是单链表，这里list原本指向的空指针就应该被改成尾插的元素，但是如果我们传一级指针，
形参的改变不会影响形参，list出了尾插的函数它任然还是一个空指针，我们要改变的是链表头的指向的地址，所以我们传二级指针过去。
这里呢？
要改变什么，我们就传什么。
这里需不需要传二级指针过去呢？
我们会不会修改到这个头节点呢？
不会，我们只需要修改的是头节点里面指向下一个元素和上一个元素的地址，我们返回的还是头节点的位置，所以我们可以不用传二级指针过去。
所以我们可以将初始化函数这么写：
ListNode* ListCreate()
{
ListNode* newnode = BuyListNode(0);
newnode->prev = newnode;
newnode->next = newnode;
return newnode;
}我们直接创建一个节点，将里面的数据记为0即可。
————
双向链表的打印
我们如何打印这个链表？
跟单链表一样，单链表我们什么时候停下来？
当遇到空，也就是说链表走完了一遍就可以停下来，那双向带头循环链表呢？
我们从表头的下一个元素走，比方说：
我们让一个指针cur开从表头往后走，每遇到一个值就打印，正因为循环，所以它到 5 的时候会回到表头，也就是 0 的位置，然后我们判断，如果 cur == 表头，那我们就可以停下来。
我们的代码就这么写：
void ListPrint(ListNode* pHead)
{
assert(pHead);
ListNode* cur = pHead->next;
while (cur!= pHead)
{
printf("%d->", cur->_data);
cur = cur->next;
}
printf("end\n");
}———-
双向链表尾插
我们知道这是一个双向循环链表，我们尾插的时候还需要注意几点；
1、最后的结构体的下一个指针应该指向表头
2、表头的上一个结构体指针应该指向最后一个结构体
我们尾插的时候，先要找到没修改前的最后一个结构体，然后得到它的地址，再让它的下一个元素指向新的结构体地址，然后再将新结构体的上一个结构体指针指向它，再修改新节点的next，头节点的prev。
代码如下：
void ListPushBack(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* newnode = BuyListNode(x);
ListNode* prev = pHead->prev;
prev->next = newnode;
newnode->prev = prev;
newnode->next = pHead;
pHead->prev = newnode;
}
别忘了断言。
具体文字操作解释：
我们先让prev指向头节点的上一个元素，这里正是我们尾节点的位置，然后我们原本尾节点的下一个指针指向我们新节点，我们新节点的上一个指针指向我们原本的尾节点。
我们新节点的下一个指针应该指向表头，也就是pHead，而pHead表头的上一个结构体应该是尾节点，我们同样赋值过去。
—————-
双向链表尾删
单链表的尾删我们拿两个指针遍历数组找最后一个元素，双向链表就不需要遍历了，因为表头的上一个结构体正是我们的尾节点，我们拿一个指针记录尾戒点的上一个结构体，然后释放尾节点，再将尾节点释放，代码如下：
void ListPopBack(ListNode* pHead)
{
assert(pHead);
ListNode* prev = pHead->prev->prev;
ListNode* cur = pHead->prev;
if (pHead->next == cur)
{
printf("NULL");
return;
}
else
{
prev->next = pHead;
pHead->prev = prev;
free(cur);
cur = NULL;
}
}
具体文字解释：
两个指针，一个指向尾节点，一个指向尾节点的上一个结构体，因为靠尾节点我们才找得到倒数第二个。
先判断链表有没有值，没有就返回，有就继续，我们让倒数第二个节点的下一个指针指向我们的表头， next = pHead，再将表头的上一个结构体指针指向倒数第二个元素，也就是pHead->prev = prev，不需要返回值。
————–
双向链表头插
就跟单链表的头插一样，只不过我们多加了个prev（链表的上一个结构体指针）而已，多赋一个值即可，但是要注意顺序，别死循环了。
void ListPushFront(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* newnode = BuyListNode(x);
ListNode* next = pHead->next;
pHead->next = newnode;
newnode->prev = pHead;
newnode->next = next;
return;
}具体文字解释：
先创建一个指针指向原本第一个结构体，因为要在它之前插入新的结构体，所以地址先存一下
新结构体的下一个结构体指针指向原本的第一个结构体
表头的下一个结构体指针指向新开辟的节点
新开辟的节点的下一个结构体指针指向原本的第一个结构体
—————
双向链表头删
既然你知道头插，也知道尾删，那头删就已经掌握了大半，看代码：
void ListPopFront(ListNode* pHead)
{
assert(pHead);
if (pHead->next == pHead)
{
printf("NULL\n");
return;
}
ListNode* cur = pHead->next;
ListNode* next = cur->next;
free(cur);
cur = NULL;
pHead->next = next;
next->prev = pHead;
return;
}具体文字解释：
新创建的结构体指针cur指向原本的第一个结构体，
next指向第二个结构体
释放cur（第一个结构体）
头节点的下一个结构体指针指向next（原本的第二个元素）
next的上一个结构体指针指向头节点
————–
双向链表查找
跟单链表一样，我们找链表里面的值判断，如果不是就继续走，如果走到了表头，我们就停下。看代码：
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
assert(pHead);
if (pHead->next == pHead)
{
printf("NULL\n");
return NULL;
}
ListNode* cur = pHead->next;
while (cur != pHead)
{
if (cur->_data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
具体文字解释：
新创建的节点cur指向表头的下一个结构体
遍历整个链表判断，如果cur不等于pHead，也就是说链表还有元素，就执行
我们比较cur里面的值，是就返回当前结构体的地址，不是就指向下一个结构体
如果遍历完还没找到，那就返回空指针
————-
双向链表在pos的前面进行插入
创建新的节点，再将这个节点与之前的节点链接起来即可：
void ListInsert(ListNode* pos, LTDataType x)
{
assert(pos);
ListNode* prev = pos->prev;
ListNode* newnode = BuyListNode(x);
newnode->prev = prev;
pos->prev = newnode;
newnode->next = pos;
prev->next = newnode;
return;
}具体文字解释：
新创建的节点prev指向我们插入节点的前一个元素
我们先让新节点的上一个元素指向prev
再将插入节点位置的pos的上一个指针指向新节点
新节点的下一个指针指向pos
prev的下一个指针指向新节点
————
删除指定节点
如果说上面的都能理解，那这是很简单的代码：
void ListErase(ListNode* pos)
{
assert(pos);
ListNode* prev = pos->prev;
ListNode* next = pos->next;
free(pos);
pos = NULL;
prev->next = next;
next->prev = prev;
return;
}文字详细解释：
prev指向删除节点的前一个元素
next指向删除节点的后一个元素
释放删除节点
链接prev和next
————-
销毁链表
void ListDestory(ListNode* pHead)
{
ListNode*cur = pHead;
ListNode*nex = pHead;
while (cur)
{
cur = cur->next;
free(nex);
nex = cur;
}
}跟单链表一样，每次删除一个并保留下一个的地址，如果为空就删完了。
————
这里放上所有代码，有需要可复制：
List.h
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int LTDataType;
typedef struct ListNode
{
LTDataType _data;
struct ListNode* next;
struct ListNode* prev;
}ListNode;
//开辟一个新的节点并返回
ListNode* BuyListNode(int x);
// 创建返回链表的头结点.
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
void ListPrint(ListNode* pHead);
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* pHead);
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* pHead);
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);List.c
#include"Lt.h"
ListNode* BuyListNode(int x)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
if (newnode == NULL)
{
printf("malloc false\n");
exit(-1);
}
newnode->_data = x;
newnode->prev = NULL;
newnode->next = NULL;
return newnode;
}
ListNode* ListCreate()
{
ListNode* newnode = BuyListNode(0);
newnode->prev = newnode;
newnode->next = newnode;
return newnode;
}
void ListPrint(ListNode* pHead)
{
assert(pHead);
ListNode* cur = pHead->next;
while (cur!= pHead)
{
printf("%d->", cur->_data);
cur = cur->next;
}
printf("end\n");
}
void ListPushBack(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* newnode = BuyListNode(x);
ListNode* prev = pHead->prev;
prev->next = newnode;
newnode->prev = prev;
newnode->next = pHead;
pHead->prev = newnode;
}
void ListPopBack(ListNode* pHead)
{
assert(pHead);
ListNode* prev = pHead->prev->prev;
ListNode* cur = pHead->prev;
if (pHead->next == cur)
{
printf("NULL");
return;
}
else
{
prev->next = pHead;
pHead->prev = prev;
free(cur);
cur = NULL;
}
}
void ListPushFront(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* newnode = BuyListNode(x);
ListNode* next = pHead->next;
pHead->next = newnode;
newnode->prev = pHead;
newnode->next = next;
return;
}
void ListPopFront(ListNode* pHead)
{
assert(pHead);
if (pHead->next == pHead)
{
printf("NULL\n");
return;
}
ListNode* cur = pHead->next;
ListNode* next = cur->next;
free(cur);
cur = NULL;
pHead->next = next;
next->prev = pHead;
return;
}
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
assert(pHead);
if (pHead->next == pHead)
{
printf("NULL\n");
return NULL;
}
ListNode* cur = pHead->next;
while (cur != pHead)
{
if (cur->_data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
void ListInsert(ListNode* pos, LTDataType x)
{
assert(pos);
ListNode* prev = pos->prev;
ListNode* newnode = BuyListNode(x);
newnode->prev = prev;
pos->prev = newnode;
newnode->next = pos;
prev->next = newnode;
return;
}
void ListErase(ListNode* pos)
{
assert(pos);
ListNode* prev = pos->prev;
ListNode* next = pos->next;
free(pos);
pos = NULL;
prev->next = next;
next->prev = prev;
return;
}
void ListDestory(ListNode* pHead)
{
ListNode*cur = pHead;
ListNode*nex = pHead;
while (cur)
{
cur = cur->next;
free(nex);
nex = cur;
}
}—————
练手
简单题
1.构建单向链表并打印
牛牛的单向链表_牛客题霸_牛客网 (nowcoder.com)
非常简单，先创建数组接收数据，然后构建链表开始尾插，最后打印
#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
int data;
struct Node* next;
}Node;
//开辟节点并返回
Node* BuyNode(int x)
{
Node* node = (Node*)malloc(sizeof(Node));
node->data = x;
node->next = NULL;
return node;
}
//尾插
void PushBack(Node** head, int x)
{
Node* node = BuyNode(x);
Node* cur = *head;
while (cur->next)
cur = cur->next;
cur->next = node;
}
//打印
void NodePrintf(Node* head)
{
Node* cur = head;
while (cur)
{
printf("%d ", cur->data);
cur = cur->next;
}
}
int main()
{
int n;
scanf("%d", &n);
int* a = (int*)malloc(sizeof(int)*n);
for (int i = 0; i<n; i++)
{
scanf("%d", &a[i]);
}
Node* node = (Node*)malloc(sizeof(Node));
//初始化...
node->data = a[0];
node->next = NULL;
//依次尾插
for (int i = 1; i < n; i++)
{
PushBack(&node, a[i]);
}
//打印
NodePrintf(node);
free(a);
return 0;
}————-
2.交换链表的首两个元素，尾两个元素
代码几乎没变，上来判断有几个元素，如果有两个，就先交换，然后再找尾交换
#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
int data;
struct Node* next;
}Node;
Node* BuyNode(int x)
{
Node* node = (Node*)malloc(sizeof(Node));
node->data = x;
node->next = NULL;
return node;
}
void PushBack(Node** head, int x)
{
Node* node = BuyNode(x);
Node* cur = *head;
while (cur->next)
cur = cur->next;
cur->next = node;
}
void NodePrintf(Node* head)
{
Node* cur = head;
while (cur)
{
printf("%d ", cur->data);
cur = cur->next;
}
}
void Reverse(Node* head)
{
Node* cur = head;
Node* prev = NULL;
//如果cur->不为空，说明至少有两个元素，交换以下
if(cur->next)
{
prev = cur;
cur = cur->next;
}
int tmp = cur->data;
cur->data = prev->data;
prev->data = tmp;
//如果cur->next为空，说明它就是最后一个元素
while(cur->next)
{
prev = cur;
cur = cur->next;
}
//交换
tmp = cur->data;
cur->data = prev->data;
prev->data = tmp;
}
int main()
{
int n;
scanf("%d", &n);
int* a = (int*)malloc(sizeof(int)*n);
for (int i = 0; i<n; i++)
{
scanf("%d", &a[i]);
}
Node* node = (Node*)malloc(sizeof(Node));
node->data = a[0];
node->next = NULL;
for (int i = 1; i < n; i++)
{
PushBack(&node, a[i]);
}
Reverse(node);
NodePrintf(node);
free(a);
return 0;
}———–
3.单链表求和
代码几乎一样，遍历求和即可
#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
int data;
struct Node* next;
}Node;
Node* BuyNode(int x)
{
Node* node = (Node*)malloc(sizeof(Node));
node->data = x;
node->next = NULL;
return node;
}
void PushBack(Node** head, int x)
{
Node* node = BuyNode(x);
Node* cur = *head;
while (cur->next)
cur = cur->next;
cur->next = node;
}
void NodePrintf(Node* head)
{
Node* cur = head;
while (cur)
{
printf("%d ", cur->data);
cur = cur->next;
}
}
void Reverse(Node* head)
{
Node* cur = head;
Node* prev = NULL;
if(cur->next)
{
prev = cur;
cur = cur->next;
}
int tmp = cur->data;
cur->data = prev->data;
prev->data = tmp;
while(cur->next)
{
prev = cur;
cur = cur->next;
}
tmp = cur->data;
cur->data = prev->data;
prev->data = tmp;
}
int main()
{
int n;
scanf("%d", &n);
int* a = (int*)malloc(sizeof(int)*n);
for (int i = 0; i<n; i++)
{
scanf("%d", &a[i]);
}
Node* node = (Node*)malloc(sizeof(Node));
node->data = a[0];
node->next = NULL;
for (int i = 1; i < n; i++)
{
PushBack(&node, a[i]);
}
int sum = 0;
while(node)
{
sum+=node->data;
node=node->next;
}
printf("%d ",sum);
free(a);
return 0;
}———
4.双链表求和
先将数组里面加起来，然后插入节点遍历打印即可
#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
int data;
struct Node* next;
}Node;
Node* BuyNode(int x)
{
Node* node = (Node*)malloc(sizeof(Node));
node->data = x;
node->next = NULL;
return node;
}
void PushBack(Node** head, int x)
{
Node* node = BuyNode(x);
Node* cur = *head;
while (cur->next)
cur = cur->next;
cur->next = node;
}
void NodePrintf(Node* head)
{
Node* cur = head;
while (cur)
{
printf("%d ", cur->data);
cur = cur->next;
}
}
void Reverse(Node* head)
{
Node* cur = head;
Node* prev = NULL;
if(cur->next)
{
prev = cur;
cur = cur->next;
}
int tmp = cur->data;
cur->data = prev->data;
prev->data = tmp;
while(cur->next)
{
prev = cur;
cur = cur->next;
}
tmp = cur->data;
cur->data = prev->data;
prev->data = tmp;
}
int main()
{
int n;
scanf("%d", &n);
int* a = (int*)malloc(sizeof(int)*n);
int i;
for (i = 0; i<n; i++)
{
scanf("%d", &a[i]);
}
for(i = 0;i<n;i++)
{
int tmp;
scanf("%d",&tmp);
a[i] += tmp;
}
Node* node = (Node*)malloc(sizeof(Node));
node->data = a[0];
node->next = NULL;
for (int i = 1; i < n; i++)
{
PushBack(&node, a[i]);
}
NodePrintf(node);
free(a);
return 0;
}正式
1. 删除链表中等于给定值 val 的所有节点。
203. 移除链表元素 – 力扣（LeetCode） (leetcode-cn.com)
这题有两种思路：
第一种，我们再开辟一个数组，如果原数组的值不等于我们要找的值，我们就开始链接下去，如果等于要找的值，我们就跳过找下一个元素，最后将最后一个元素的next = NULL。
这种思路较为简单，但是因为需要再开辟一个链表，所以它会有额外的空间消耗。
第二种，我们拿两个指针，一个快一步，一个慢一点，比如示例1中，我的快指针指向了6，而我的慢指针还指向的是2，那我们就直接让2的next指向3，然后释放6的空间，这样的好处就是不用在开辟空间，下面我们看代码实现：
第一种：
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* newhead,*newtail;
newhead = newtail = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* cur = head;
while(cur)
{
if(cur->val != val)
{
newtail->next = cur;
newtail = newtail->next;
cur = cur->next;
}
else
{
cur = cur->next;
}
}
newtail->next = NULL;
return newhead->next;
}第二种：
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* cur = head;
struct ListNode* hhead = NULL;
while(cur)
{
if(cur->val != val)
{
hhead= cur;
cur= cur->next;
}
else
{
struct ListNode* next = cur->next;
if(hhead == NULL)
{
free(cur);
head = next;
cur= next;
}
else
{
free(cur);
hhead->next = next;
cur=next;
}
}
}
return head;
}————-
2. 反转一个单链表。
206. 反转链表 – 力扣（LeetCode） (leetcode-cn.com)
同样两种方法：
第一种，我们用三个指针，第一个指针指向空，第二个指针指向第一个指针，第三个指针指向第二个指针的下一个元素，以图举例，第一个指针为NULL，第二个指针是1，第三个指针是2，我们让1指向NULL,然后2指向1，然后我们将2的值给1，3的值给2，让它们指向下一个元素。
第二种，类似头插，我们让一个指针为NULL，然后我们让数组的第一个元素头插进去，第二个也头插进去，第三个也头插进去…返回最后一个头插的地址即可，看代码：
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* n1,*n2,*n3;
if(head == NULL)
{
return NULL;
}
n1 = NULL;
n2 = head;
n3 = head->next;
while(n2)
{
n2->next = n1;
n1 = n2;
n2 = n3;
if(n3)
{
n3 = n3->next;
}
}
return n1;
}第二种：
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* cur = head;
struct ListNode* newhead =NULL;
while(cur)
{
struct ListNode* next = cur->next;
cur->next = newhead;
newhead = cur;
cur=cur->next;
}
return newhead;
}———–
3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个 中间结点。
876. 链表的中间结点 – 力扣（LeetCode） (leetcode-cn.com)
同样，两种办法：
第一种，比较简单粗暴，我们先计算链表长度，然后除2，让头指针走这么多步再返回。
第二种，我们两个指针，一个快一个慢，快的一次走两步，慢的一次走一步，当快的指针走向尾部的时候慢的指针才走一半，我们返回慢的指针即可。
看代码实现：
第一种：
struct ListNode* middleNode(struct ListNode* head)
{
int count = 0;
struct ListNode* cur = head;
while(cur)
{
count++;
cur = cur->next;
}
count /= 2;
cur = head;
while(count--)
{
cur = cur->next;
}
return cur;
}第二种：
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* show = head;
struct ListNode* fast = head;
while(fast&&fast->next)
{
show = show->next;
fast = fast->next->next;
}
return show;
}———-
4、输入一个链表，输出该链表中倒数第k个结点。
剑指 Offer 22. 链表中倒数第k个节点 – 力扣（LeetCode） (leetcode-cn.com)
这题解法就比较单一，我们还是用双指针的思路，倒数第k个节点，我们就让快的指针先走k次，然后慢的指针再开始走，最后返回慢指针即可，看代码实现：
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
{
// write code here
struct ListNode* cur = pListHead;
while(k-- != 0)
{
if(cur == NULL)
{
return NULL;
}
cur=cur->next;
}
struct ListNode* prev = pListHead;
while(cur)
{
cur = cur->next;
prev = prev->next;
}
return prev;
}————
5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
21. 合并两个有序链表 – 力扣（LeetCode） (leetcode-cn.com)
如果常见有做过一道合并两个数组的题的话，那这里就可以用到其中的思路，就是我们先比较两个的值，把值小的先放进去，然后再让那个往下走一步，这里也可以用这种思路：
第一个指针指向list1 – 1，第二个指向list2 – 1，我们比较，一样大，我们就随便放一个进去，比如我这里放list2，然后list 2 = list2->next;然后我们在再比一次，如果其中一个为空了，我们就可以停下，然后判断，如果list1还有，我们就让最后的指针指向list1，如果list2还有，就指向list2，如果都没有，就置为空。
看代码实现：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
struct ListNode cur = {0};
struct ListNode* prev = &cur;
while(list1&&list2)
{
if(list1->val>list2->val)
{
prev->next = list2;
list2 = list2->next;
}
else
{
prev->next = list1;
list1=list1->next;
}
prev=prev->next;
}
if(list1)
{
prev->next = list1;
}
else if(list2)
{
prev->next=list2;
}
else
{
prev->next = NULL;
}
return cur.next;
}———-
6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。
这题就比较阴间，为什么这么说，不仅因为它不支持c，而且它还没有给图，全靠我们想，这里给大家画图理解一下：
这是它提供给我们的链表，我们要返回的是这样的：
这里就说思路，我们拿两个指针开始遍历数组，第一个指针放的都是小于x的，第二个放的都是大于x的，然后我们再把它们连起来，具体看代码实现：
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
// write code here
ListNode*lessHead,*lessEnd,*greatHead,*greatEnd;
lessHead = lessEnd = (ListNode*)malloc(sizeof(ListNode));
greatHead = greatEnd = (ListNode*)malloc(sizeof(ListNode));
lessEnd->next = greatEnd->next=NULL;
ListNode*cur = pHead;
while(cur)
{
if(cur->val < x)
{
lessEnd->next = cur;
lessEnd = lessEnd->next;
}
else
{
greatEnd->next = cur;
greatEnd = greatEnd->next;
}
cur = cur->next;
}
lessEnd->next = greatHead->next;
greatEnd->next = NULL;
ListNode*list = lessHead->next;
free(lessHead);
free(greatHead);
return list;
}
};上来我们开辟四个指针，其中两个是我们头，两个是我们的尾，我们需要尾去走，然后记住头来链接。
———–
7. 链表的回文结构。
链表的回文结构_牛客题霸_牛客网 (nowcoder.com)
两种办法：
第一种比较搓，我们开辟一个数组，数组里面是我们链表的val，然后比较数组的值再返回，因为靠开辟的是数组，所以实现起来相当简单,但是实际上我们是取巧了的，不建议适用这种办法，但是如果实在做不出来，还是可以用的，不管多搓，能做出来就算成功。
第二种，我们先找到链表中间的位置，然后我们再将链表后面的位置反转，然后再一个一个比较，因为反转链表我们之前写过，所以我直接拿来用了，具体实现看代码：
第一种：
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
// write code here
int arr[900];
int count = 0;
ListNode* cur = A;
while(cur)
{
arr[count++] = cur->val;
cur = cur->next;
}
int left=0,right=count-1;
while(left<right)
{
if(arr[left]== arr[right])
{
left++;
right--;
}
else
{
return false;
}
}
return true;
}
};第二种：
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
// write code here
ListNode* show,*fast;
show = fast = A;
while(fast&&fast->next)
{
show = show->next;
fast = fast->next->next;
}
show = reverseList(show);
ListNode* head = A;
while(show&&show->next)
{
if(head->val == show->val)
{
head = head->next;
show = show->next;
}
else
{
return false;
}
}
return true;
}
};这里得提一下，就是反转链表只能用三指针，因为你用第二种相当于在函数内部开辟了一个新节点返回节点的头，但出了函数节点头就找不到了，所以会报错，注意下就好。
———
8.输入两个链表，找出它们的第一个公共结点。
160. 相交链表 – 力扣（LeetCode） (leetcode-cn.com)
两种思路：
第一种时间复杂度是O（n^2），大家看到这个时间复杂度就应该知道是什么办法了，就是拿a的每一个元素都跟b比，知道链表结束。
第二种：我们先看两个链表长度，我们让长的先走，这里我们看图，b很明显长一些，我们就让b先走，让它从b2开始比，然后同时往后走，碰到相交就停下返回，看代码实现：
第一种：
不推荐使用，看着简单，但链表一长太耗时
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
for(struct ListNode* a = headA;a!= NULL;a = a->next)
{
for(struct ListNode* b = headB;b!= NULL;b = b->next)
{
if(a == b)
{
return a;
}
}
}
return NULL;
}第二种：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
struct ListNode* cura = headA;
struct ListNode* curb = headB;
int count=0,count1=0,count2=0;
while(cura)
{
count1++;
cura = cura->next;
}
while(curb)
{
count2++;
curb=curb->next;
}
if(count1<count2)
{
curb = headA;
cura = headB;
}
else
{
cura = headA;
curb = headB;
}
count = abs(count1-count2);
while(count--)
{
if(cura)
{
cura = cura->next;
}
}
while(cura&&curb)
{
if(cura == curb)
{
return cura;
}
else
{
cura = cura->next;
curb = curb->next;
}
}
return NULL;
}———-
9. 给定一个链表，判断链表中是否有环。
141. 环形链表 – 力扣（LeetCode） (leetcode-cn.com)
很简单的一题，我们两个指针遍历链表，慢的一次一步，快的一次两步，什么时候慢的等于快的，就说明有环，如果没有环就直接返回，看代码：
bool hasCycle(struct ListNode *head)
{
struct ListNode* show,*fast;
fast = show = head;
while(fast &&fast->next)
{
show=show->next;
fast = fast->next->next;
if(fast == show)
{
return true;
}
}
return false;
}———-
10. 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL
142. 环形链表 II – 力扣（LeetCode） (leetcode-cn.com)
这题更是重量级，这里说两种思路：
第一种，看图：
这是我们已有的，我们拿两个快慢指针：
同时从这里开始走，当show和fast相遇的时候，它们肯定在环里面，我们假设是这里：
我们让这个地方断开，让这里指向空，然后我们从下一个位置开始走，然后head开始走，当它们重合的时候，就是环的入口，看图；
第二种：
我们可以看到，show走的路程是L+X，而fast走的路程是 L + NC+C-X
N是圈数，简答来说，就是，当一个指针从fast和show相遇的地方走，另一个指针从head开始走，它们一定会相遇在环的入口处。
我推荐使用第一种，因为简单易懂，第二种理解起来比较麻烦，但如果问起，这也是一种解决办法。
看代码实现：
第一种：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
struct ListNode* cura = headA;
struct ListNode* curb = headB;
int count=0,count1=0,count2=0;
while(cura)
{
count1++;
cura = cura->next;
}
while(curb)
{
count2++;
curb=curb->next;
}
if(count1<count2)
{
curb = headA;
cura = headB;
}
else
{
cura = headA;
curb = headB;
}
count = abs(count1-count2);
while(count--)
{
if(cura)
{
cura = cura->next;
}
}
while(cura&&curb)
{
if(cura == curb)
{
return cura;
}
else
{
cura = cura->next;
curb = curb->next;
}
}
return NULL;
}
struct ListNode *detectCycle(struct ListNode* head)
{
struct ListNode* show,*fast;
struct ListNode* cur = NULL;
show = fast = head;
while(fast &&fast->next)
{
show = show->next;
fast = fast->next->next;
if(fast == show)
{
cur = fast->next;
fast->next = NULL;
}
}
struct ListNode* prev = head;
struct ListNode*pos = getIntersectionNode(prev,cur);
if(pos)
{
return pos;
}
else
return NULL;
}第二种：
struct ListNode *detectCycle(struct ListNode* head)
{
struct ListNode* show,*fast;
struct ListNode* cur = NULL;
show = fast = head;
while(fast &&fast->next)
{
show = show->next;
fast = fast->next->next;
if(show == fast)
{
struct ListNode* meet = show;
struct ListNode* start = head;
while(meet != start)
{
start = start->next;
meet = meet->next;
}
return meet;
}
}
return NULL;
}11.两数相加
2. 两数相加 – 力扣（LeetCode） (leetcode-cn.com)
先说思路，我们拿两个指针分别开始走这两个链表，再拿两个值记录这里面的值，再拿一个值记录进位，把这两个链表的值相加，如果这个值大于9，我们就放0，然后让计数+1，下一次计算相加的时候就加1，如果下一次的值不大于9，那加完就让计数变为0
//插入节点函数
struct ListNode* BuyNoude(int x)
{
struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
newnode->val = x;
newnode->next = NULL;
return newnode;
}
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
{
//两个指针开始对应两个链表
struct ListNode* cur1 = l1;
struct ListNode* cur2 = l2;
//要返回的新链表
struct ListNode* cur,*head;
//计算进位
int count = 0;
//带哨兵位，其中一个往后走，另一个在头节点不变，等会就返回这个
cur = head = (struct ListNode*)malloc(sizeof(struct ListNode));
//判断循环条件，如果两个链表都为空才停下
while(cur1 || cur2)
{
//计算里面的值，如果是空链表就算0
int c1 = cur1==NULL?0:cur1->val;
int c2 = cur2==NULL?0:cur2->val;
//相加，count不进位情况为0，所以不影响
int sum = c1+c2+count;
//比较
if(sum<10)
{
//尾插一个
cur->next = BuyNoude(sum%10);
cur = cur->next;
//将计数变为0
count = 0;
}
else
{
//如果大于9，我们就尾插一个0进去，表示进位，下一次计算就多加count/10，也就是1
cur->next = BuyNoude(sum-10);
cur = cur->next;
count = sum/10;
}
//让两个链表往下走
if(cur1!=NULL)//l1不为空，链接到下一节点
cur1=cur1->next;
if(cur2!=NULL)//l2不为空，链接到下一节点
cur2=cur2->next;
}
//判断，此时count如果还有，就意味着没进位，所以再链接一下
if(count != 0)
{
cur->next = BuyNoude(count);
}
return head->next;
}——–
希望以上的题能对你学习起到帮助，如果有兴趣可以点开我的专栏看更多，谢谢您的观看。
今天的文章【数据结构】链表分享到此就结束了，感谢您的阅读。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/8447.html
