数据结构-＞链表分类与oj（题），带你提升代码好感
✅作者简介：大家好，我是橘橙黄又青，一个想要与大家共同进步的男人😉😉
🍎个人主页：橘橙黄又青-CSDN博客
1.🍎链表的分类
前面我们学过顺序表，顺序表问题：
- 1. 中间/头部的插入删除，时间复杂度为O(N)
- 2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
- 3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到 200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
这些问题，链表给出了相应的答案。
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表 中的指针链接次序实现的 。
比如说我们前面学习的单链表就是如此。
单链表是单向不循环不带头链表
实际中要实现的链表的结构非常多样，以下情况组合起来就有8种链表结构：
- 1. 单向、双向
- 2. 带头、不带头
- 3. 循环、非循环
又称2x2x2
图解：
- 1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结 构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
- 2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都 是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带 来很多优势，实现反而简单了，后面我们代码实现了就知道了。
2.🍎链表相关基础oj
| 题目 | 链接 |
|---|---|
| 设计链表 | . - 力扣（LeetCode） |
| 两数相加 | . - 力扣（LeetCode） |
| 合并两个有序链表 | . - 力扣（LeetCode） |
| 两两交换链表中的节点 | . - 力扣（LeetCode） |
| 删除排序链表中的重复元素 | . - 力扣（LeetCode） |
| 删除排序链表中的重复元素II | . - 力扣（LeetCode） |
| 相交链表 | . - 力扣（LeetCode） |
| 移除链表元素 | . - 力扣（LeetCode） |
| 回文链表 | . - 力扣（LeetCode） |
| 奇偶链表 | . - 力扣（LeetCode） |
| 链表的中间结点 | . - 力扣（LeetCode） |
| 链表最大孪生和 | . - 力扣（LeetCode） |
| 两两交换链表中的节点 | 404: This page could not be found |
合并两个链表中，可以安排一个哨兵（头）可以减少判断空的代码。
哨兵位的申请：
这些都是比较好的题目，
接下来我们分析几道题目
| 题目 | 链接 |
|---|---|
| 反转链表 | . - 力扣（LeetCode） |
| 反转链表II | . - 力扣（LeetCode） |
| 链表中间节点问题 | . - 力扣（LeetCode） |
| 环形链表的约瑟夫问题 | 环形链表的约瑟夫问题_牛客题霸_牛客网 |
2.1🍎第一个反转链表
第一种：头插法
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
//头插术
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
ListNode* returnHead = NULL;
ListNode* ListLt = head;
while(ListLt != NULL){
//保存下一个节点
ListNode* temp = ListLt -> next;
//换头手术
ListLt -> next = returnHead;
returnHead = ListLt;
//迭代
ListLt = temp;
}
return returnHead;
}这里说一个错误代码：
输出结果为1，为什么来：
所以temp要保存下一个节点。
第二种解法：
三指针法：
代码：
/**
* 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;
ListNode* pcur = head;
while(n2){
n2-> next = n1;
n1 = n2;
n2 = n3;
if(n3){//这里防止n3为空，如果为空就无next
n3 = n3 -> next;
}
}
return n1;
}图解：
链表II与这个差不多，思路更为复杂。
2.2🍎链表中间节点问题
可以遍历链表计数除2，也可以使用双指针法
双指针法：
思路：
代码：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
ListNode* slow,*fast;
slow = fast = head;
while(fast && fast -> next){
slow = slow -> next;
fast = fast -> next -> next;
}
return slow;
}值得注意的是循环条件不能写成 fast -> next &&fast ，原因是计算机编译器是从左往右编译的，如果fast为空，就没有fast -> next。
快慢指针法以后会经常使用务必理解.
2.3.环形链表的约瑟夫问题
题目:
这里我们输入Li 它就有暗示，说明已经有结构体结构了
解题代码：
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int整型
* @param m int整型
* @return int整型
*/
typedef struct ListNode ListNode;
//申请一个节点
ListNode* BuyNode(int x){
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode -> val = x;
newNode -> next = NULL;
return newNode;
}
ListNode* creteList(int n){
ListNode* phead = BuyNode(1);
ListNode* ptail = phead;
//创建链表和标号
for (int i = 2; i <= n; i++) {
ptail -> next = BuyNode(i);
ptail = ptail -> next;
}
//链表首尾链接
ptail -> next = phead;
return phead;
}
#include <stdio.h>
int ysf(int n, int m ) {
//逢m删除节点
ListNode* head = creteList(n);
ListNode* pcur = head;
//前驱节点
ListNode* prev = NULL;
int conut = 1;
while (pcur ->next != pcur) {
if(conut == m){
//删除当前节点
prev -> next = pcur ->next;
free(pcur);
//删除节点后往后走，让pcur走到新的位置，conut为初始值
pcur = prev -> next;
conut = 1;
}
else{
//pcur往后走
prev = pcur;
pcur = pcur -> next;
conut++;
}
}
//此时pcur节点就是活下来的节点
return pcur -> val;
}
试试效果：
3.🍎上节链表代码建议重复观看
SList.c文件：
SList.h文件
test.c文件测试代码：
test.c文件代码
#include"SList.h"
//void SlistTest01() {
//
// 链表的打印
// SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
// node1->data = 1;
// SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
// node2->data = 2;
// SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
// node3->data = 3;
// SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
// node4->data = 4;
//
// node1->next = node2;
// node2->next = node3;
// node3->next = node4;
// node4->next = NULL;
//
// SLTNode* plist = node1;
// SLTPrint(plist);
//}
void SlistTest02() {
//尾插测试
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist); //1->2->3->4->NULL
//头插测试
//SLTPushFront(&plist, 5);
//SLTPrint(plist); //5->1->2->3->4->NULL
//SLTPushFront(&plist, 6);
//SLTPrint(plist); //6->5->1->2->3->4->NULL
//SLTPushFront(&plist, 7);
//SLTPrint(plist); //7-6->5->1->2->3->4->NULL
SLTPopBack(&plist);
SLTPrint(plist);//1->2->3->NULL
SLTPopBack(&plist);
SLTPrint(plist);//1->2->3->NULL
SLTPopBack(&plist);
SLTPrint(plist);//1->2->3->NULL
SLTPopBack(&plist);
SLTPrint(plist);//1->2->3->NULL
SLTPopBack(&plist);
SLTPrint(plist);//1->2->3->NULL
}
void SlistTest03() {
SLTNode* plist = NULL;
SLTPushBack(&plist, 1);
SLTPushBack(&plist, 2);
SLTPushBack(&plist, 3);
SLTPushBack(&plist, 4);
SLTPrint(plist); //1->2->3->4->NULL
SListDesTroy(&plist);
头删
//SLTPopFront(&plist);
//SLTPrint(plist); //2->3->4->NULL
//SLTPopFront(&plist);
//SLTPrint(plist); //3->4->NULL
//SLTPopFront(&plist);
//SLTPrint(plist); //4->NULL
//SLTPopFront(&plist);
//SLTPrint(plist); //NULL
//SLTPopFront(&plist);
//SLTPrint(plist); //assert
//查找测试
//SLTNode* FindRet = SLTFind(&plist, 3);
//if (FindRet) {
// printf("找到了！\n");
//}
//else {
// printf("未找到！\n");
//}
//SLTInsert(&plist, FindRet, 100);
//SLTInsertAfter(FindRet, 100);
//删除指定位置的节点测试
//SLTErase(&plist, FindRet);
//SLTPrint(plist); //1->2->3->NULL
}
int main() {
//SlistTest01();
//SlistTest02();
SlistTest03();
return 0;
}SList.c文件代码：
#include"SList.h"
//打印
void SLTPrint(SLTNode* phead) {
SLTNode* pcur = phead;
while (pcur)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}
//开辟空间
SLTNode* SLTBuyNode(SLTDataType x) {
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL) {
perror("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
//
void SLTPushBack(SLTNode** pphead, SLTDataType x) {
assert(pphead);
//开辟空间
SLTNode* newnode = SLTBuyNode(x);
//链表为空，新节点作为phead
if (*pphead == NULL) {
*pphead = newnode;
return;
}
//链表不为空，找尾节点
SLTNode* ptail = *pphead;
while (ptail->next)
{
ptail = ptail->next;
}
//ptail就是尾节点
ptail->next = newnode;
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x) {
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
//newnode *pphead
newnode->next = *pphead;
*pphead = newnode;
}
//尾删
void SLTPopBack(SLTNode** pphead) {
assert(pphead);
//链表不能为空
assert(*pphead);
//链表不为空
//链表只有一个节点，有多个节点
if ((*pphead)->next == NULL) {
free(*pphead);
*pphead = NULL;
return;
}
SLTNode* ptail = *pphead;
SLTNode* prev = NULL;
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}
prev->next = NULL;
//销毁尾结点
free(ptail);
ptail = NULL;
}
//头删
void SLTPopFront(SLTNode** pphead) {
assert(pphead);
//链表不能为空
assert(*pphead);
//让第二个节点成为新的头
//把旧的头结点释放掉
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x) {
assert(pphead);
//遍历链表
SLTNode* pcur = *pphead;
while (pcur) //等价于pcur != NULL
{
if (pcur->data == x) {
return pcur;
}
pcur = pcur->next;
}
//没有找到
return NULL;
}
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
assert(pphead);
assert(pos);
//要加上链表不能为空
assert(*pphead);
SLTNode* newnode = SLTBuyNode(x);
//pos刚好是头结点
if (pos == *pphead) {
//头插
SLTPushFront(pphead, x);
return;
}
//pos不是头结点的情况
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
//prev -> newnode -> pos
prev->next = newnode;
newnode->next = pos;
}
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
//pos newnode pos->next
newnode->next = pos->next;
pos->next = newnode;
}
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos) {
assert(pphead);
assert(*pphead);
assert(pos);
//pos刚好是头结点，没有前驱节点，执行头删
if (*pphead == pos) {
//头删
SLTPopFront(pphead);
return;
}
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
//prev pos pos->next
prev->next = pos->next;
free(pos);
pos = NULL;
}
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos) {
assert(pos);
//pos->next不能为空
assert(pos->next);
//pos pos->next pos->next->next
SLTNode* del = pos->next;
pos->next = pos->next->next;
free(del);
del = 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
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
//链表是由节点组成
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
//typedef struct SListNode 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** pphead, SLTDataType x);
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesT今天就到这里了，都看到这里了，点一个赞吧，感谢观看。