🌈个人主页：小新_-

🎈个人座右铭：“成功者不是从不失败的人，而是从不放弃的人！”🎈

🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝

🏆所属专栏： 数据结构与算法欢迎订阅，持续更新中~~~

                      

         ✨让小新带着你快乐的学习吧~✨

目录

1. 链表的概念及结构

2、单链表的实现

准备工作

1、单链表的插入

1）头插

2）尾插

3）指定位置前插

4）指定位置后插

2、单链表的删除

1）头删

2）尾删

3）删除指定位置节点

4）删除指定位置之后节点

3、单链表的查找

4、单链表的销毁

3、链表的分类

4、 链表经典算法OJ题⽬

3.1 单链表相关经典算法OJ题1：移除链表元素(点击进入题目)

3.2 单链表相关经典算法OJ题2：反转链表（点击进入题目）

3.3 单链表相关经典算法OJ题3：合并两个有序链表（点击进入题目）

3.4 单链表相关经典算法OJ题4：链表的中间结点（点击进入题目）

3.5 循环链表经典应⽤-环形链表的约瑟夫问题（点击进入题目）

3.6 单链表相关经典算法OJ题5：分割链表（点击进入题目）

---

1. 链表的概念及结构

2、单链表的实现

准备工作

单链表实现前，有几个小段代码和问题

1、首先，我们来搞懂一个一个概念上的问题，就是节点的实参形参问题，其实就是考验对指针的理解与掌握

2、申请新的节点

代码比较简单，用malloc函数申请新节点的空间，让新节点的的data域置为x,next域为空

SLTNode* SLNewNode(SLDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));newnode->Data = x;newnode->next = NULL;return newnode;
}

3、打印当前链表

上代码

void SLPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->Data);pcur = pcur->next;}printf("NULL");
}

4、单链表的声明

typedef int SLDataType;
typedef struct SListNode
{SLDataType Data;struct SListNode* next;
}SLTNode;

1、单链表的插入

1）头插

分析：

尾删思路比较简单，我们有头结点的指针phead，我们让我们新申请的节点的next指针，指向原来的头结点，就完成了，我们考虑一下特殊情况，如果链表为空，怎么办？那还不简单，直接成为新的节点，代码就跟不是空表一样，so easy!小小头插，拿下拿下。

void SLPushFront(SLTNode** pphead, SLDataType x)
{assert(pphead);SLTNode* newnode = SLNewNode(x);newnode->next = *pphead;*pphead = newnode;}

2）尾插

分析：

如图，我们想插入一个元素4，如何插入呢？首先，我们得找到原尾节点吧。然后让原尾节点的next指针指向4这个新节点，这样我们的4就成为了尾节点，再让4的next指针指向NULL。但有一个问题，那就是如果链表为空怎么办？那就没有尾节点了。直接将这个节点作为我们的新节点。所以，大体思路就是，先判断链表是否为空，如果是就直接作为新的节点，如果不是，我们就先找到尾节点，然后执行插入操作就可以了。

代码如下：

void SLPushBack(SLTNode** pphead, SLDataType x)
{assert(pphead);SLTNode* newnode = SLNewNode(x);//链表为空，作为结点if (*pphead == NULL){*pphead = newnode;return;}//链表不为空，寻找尾节点SLTNode* ptail = *pphead;//寻找尾节点while (ptail->next){ptail = ptail->next;}//ptail就是尾节点ptail = newnode;
}

3）指定位置前插

分析：

我们看到，要想在pos(3)之前插入，我们就要找到pos之前的节点prev，prev的next指向newnode，newnode的next指向pos。考虑特殊情况，当pos是头结点时，就没有prev，怎么办呢？我们可以直接调用头插即可。

代码如下：

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x)
{assert(pphead);assert(pos);assert(*pphead);SLTNode* newnode=  SLNewNode(x);//如果pos是头结点if (pos == *pphead){SLPushFront(newnode, x);return;}SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = newnode;newnode->next = pos;
}

4）指定位置后插

分析：

指定位置后插比指定位置前插较为简单，但要注意的是顺序，如果先把pos的next给newnode,newnode中的next保存的是pos的下一个节点地址，然后再将newnode的next指向下一节点，这样导致pos的next不再指向真正的下一节点。而应该先把pos的next赋值给newnode的next,再将pos的next指向newnode.

代码如下：

2、单链表的删除

1）头删

分析：

头删比较简单，将原来的第二个节点作为新链表的第一个节点，并将原来第一个节点释放掉,并将next赋给pphead

代码如下：

void SLPopFront(SLTNode** pphead)//头删
{assert(pphead);//链表不为空assert(*pphead);//->指向第一个节点的地址SLTNode* next = (*pphead)->next;free(*pphead);(*pphead) = next;
}

2）尾删

分析：

既然要进行删除操作，那么链表至少得有一个节点吧，所以得提前判断一下。要进行尾删，首先，我们要找到尾节点的前一个节点，我们就叫他prev吧，让prv不再指向尾节点的next域，而是NULL，然后将尾节点用free函数将尾节点的内存还给操作系统。但只有一个节点的时候呢？我们只能将该节点释放掉咯（没办法的事，无奈）

void SLPopBack(SLTNode** pphead)
{assert(pphead);//链表不为空assert(*pphead);//->指向第一个节点的地址while ((*pphead)->next==NULL)//如果只有一个节点{free(*pphead);*pphead = NULL;return;}//具有多个节点SLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next){prev = ptail;ptail=ptail->next;}//找到prev了prev->next = NULL;free(ptail);
ptail=NULL//别忘了置空，以免疯狗乱咬人（狗头 狗头）
}

3）删除指定位置节点

分析：

删除指定位置的节点，我们定义一个指针prev，让prev找到pos之前的节点（寻找prev的循环条件：prev->next !=pos），此时，将prev的next指针指向pos的下一个节点，再将pos释放掉。注意，顺序不能颠倒！！！需要注意的是特殊情况，当pos就是头结点。此时没有prev，我们可以直接执行头删操作。

代码如下：

void SLErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead);assert(pos);if (pos == *pphead){SLPopFront(pphead);return;}SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}(prev->next) = (pos->next);free(pos);pos = NULL;
}

4）删除指定位置之后节点

分析：

思路比较清晰，看图一目了然，将pos的next指针指向pos下一个节点的下一个节点

代码如下：

void SLEraseAfter(SLTNode* pos)
{assert(pos);assert(pos->next);pos->next = pos->next->next;free(pos->next);pos->next = NULL;
}

3、单链表的查找

没什么好说的，上代码

SLTNode* SLTFind(SLTNode** pphead, SLDataType x)
{assert(pphead);//遍历链表SLTNode* pcur = *pphead;while (pcur) //等价于pcur != NULL{if (pcur->Data == x) {return pcur;}pcur = pcur->next;}//没有找到return NULL;
}

4、单链表的销毁

上代码

void SListDesTroy(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

完整代码如下

sqlist.c

#define _CRT_SECURE_NO_WARNINGS 1
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"void SLPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->Data);pcur = pcur->next;}printf("NULL\n");
}
SLTNode* SLNewNode(SLDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));newnode->Data = x;newnode->next = NULL;return newnode;
}
void SLPushBack(SLTNode** pphead, SLDataType x)
{assert(pphead);SLTNode* newnode = SLNewNode(x);//链表为空，作为结点if (*pphead == NULL){*pphead = newnode;return;}//链表不为空，寻找尾节点SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}//ptail就是尾节点ptail = newnode;
}
void SLPushFront(SLTNode** pphead, SLDataType x)
{assert(pphead);SLTNode* newnode = SLNewNode(x);newnode->next = *pphead;*pphead = newnode;
}
void SLPopBack(SLTNode** pphead)
{assert(pphead);//链表不为空assert(*pphead);//->指向第一个节点的地址while ((*pphead)->next==NULL)//如果只有一个节点{free(*pphead);*pphead = NULL;return;}//具有多个节点SLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next){prev = ptail;ptail=ptail->next;}//找到prev了prev->next = NULL;free(ptail);
}
void SLPopFront(SLTNode** pphead)//头删
{assert(pphead);//链表不为空assert(*pphead);//->指向第一个节点的地址SLTNode* next = (*pphead)->next;free(*pphead);(*pphead) = next;
}//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x)
{assert(pphead);assert(pos);assert(*pphead);SLTNode* newnode=  SLNewNode(x);//如果pos是头结点if (pos == *pphead){SLPushFront(newnode, x);return;}SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = newnode;newnode->next = pos;
}
//在指定位置之后插入数据
void SLInsertAfter(SLTNode* pos, SLDataType x)
{assert(pos);SLTNode* newnode = SLNewNode(x);newnode->next = pos->next;pos->next = newnode;
}
//删除pos节点
void SLErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead);assert(pos);if (pos == *pphead){SLPopFront(pphead);return;}SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}(prev->next) = (pos->next);free(pos);pos = NULL;
}
//删除pos之后的节点
void SLEraseAfter(SLTNode* pos)
{assert(pos);assert(pos->next);pos->next = pos->next->next;free(pos->next);pos->next = NULL;
}
SLTNode* SLTFind(SLTNode** pphead, SLDataType x)
{assert(pphead);//遍历链表SLTNode* pcur = *pphead;while (pcur) //等价于pcur != NULL{if (pcur->Data == x) {return pcur;}pcur = pcur->next;}//没有找到return NULL;
}
//销毁链表
void SListDesTroy(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

slist.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDataType;
typedef struct SListNode
{SLDataType Data;struct SListNode* next;
}SLTNode;
void SLPrint(SLTNode* phead);
SLTNode* SLNewNode(SLDataType x);
void SLPushBack(SLTNode** phead, SLDataType x);
void SLPushFront(SLTNode** phead, SLDataType x);
void SLPopBack(SLTNode** pphead);
void SLPopFront(SLTNode** pphead);
SLTNode* SLFind(SLTNode** pphead, SLDataType x);//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLDataType x);//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);//销毁链表
void SListDesTroy(SLTNode** pphead);

测试文件这里就不包含了，读者朋友可以自己写代码的时候测试

3、链表的分类

如下：

思路：建立大小链表，大于x放大链表，小于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(head==NULL){return head;
}
ListNode* newHeadLess,*newTailLess,*newHeadGreagter,*newTailGreagter;newHeadLess=newTailLess=(ListNode*)malloc(sizeof(ListNode));
newHeadGreagter=newTailGreagter=(ListNode*)malloc(sizeof(ListNode));ListNode* pcur=head;
while(pcur){if(pcur->val<x){newTailLess->next=pcur;newTailLess=newTailLess->next;}else{newTailGreagter->next=pcur;newTailGreagter=newTailGreagter->next;}pcur=pcur->next;
}newTailGreagter->next=NULL;newTailLess->next=newHeadGreagter->next;ListNode*ret=newHeadLess->next;free(newHeadGreagter);free(newHeadLess);return ret;
}

 

最后，感谢大家的观看~~