加快公司网站建设,石家庄网址服务,简单网站建设 有教程视频,wordpress小说网站模板下载地址✅作者简介#xff1a;大家好#xff0c;我是橘橙黄又青#xff0c;一个想要与大家共同进步的男人#x1f609;#x1f609;
#x1f34e;个人主页#xff1a;橘橙黄又青-CSDN博客
1.#x1f34e;链表的分类
前面我们学过顺序表#xff0c;顺序表问题#xff1a; …
✅作者简介大家好我是橘橙黄又青一个想要与大家共同进步的男人
个人主页橘橙黄又青-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为空如果为空就无nextn3 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文件代码
#includeSList.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-NULLSLTPopBack(plist);SLTPrint(plist);//1-2-3-NULLSLTPopBack(plist);SLTPrint(plist);//1-2-3-NULLSLTPopBack(plist);SLTPrint(plist);//1-2-3-NULLSLTPopBack(plist);SLTPrint(plist);//1-2-3-NULLSLTPopBack(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-NULLSListDesTroy(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文件代码
#includeSList.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);//链表为空新节点作为pheadif (*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 *ppheadnewnode-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 - posprev-next newnode;newnode-next pos;
}
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* newnode SLTBuyNode(x);//pos newnode pos-nextnewnode-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-nextprev-next pos-next;free(pos);pos NULL;
}
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos) {assert(pos);//pos-next不能为空assert(pos-next);//pos pos-next pos-next-nextSLTNode* 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
#includestdio.h
#includestdlib.h
#includeassert.htypedef 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
今天就到这里了都看到这里了点一个赞吧感谢观看。
