做网站运营有前途么,大淘客怎么做网站,黑龙江省公共资源,如何创建自己公司网站目录
一、链表的概念及结构
二、链表的分类
三、单链表的实现
建立链表的节点#xff1a;
尾插——尾删#xff1a;
头插——头删#xff1a;
查找#xff1a;
指定位置之后删除——插入#xff1a;
指定位置之前插入——删除指定位置#xff1a;
销毁链表
尾插——尾删
头插——头删
查找
指定位置之后删除——插入
指定位置之前插入——删除指定位置
销毁链表
打印
四、链表面试题
五、总体代码 一、链表的概念及结构 概念链表是一种 物理存储结构上非连续 、非顺序的存储结构数据元素的 逻辑顺序 是通过链表 中的 指针链接 次序实现的 。 二、链表的分类 实际中链表的结构非常多样以下情况组合起来就有 8 种链表结构 1. 单向或者双向 2. 带头或者不带头 3. 循环或者非循环 虽然有这么多的链表的结构但是我们实际中最常用还是两种结构 1. 无头单向非循环链表 结构简单 一般不会单独用来存数据。实际中更多是作为 其他数据结 构的子结构 如哈希桶、图的邻接表等等。另外这种结构在 笔试面试 中可能出现比较多。 2. 带头双向循环链表 结构最复杂 一般用在单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带来很多优势实现反而简单了。 三、单链表的实现
建立链表的节点
链表中的节点结构体大概有这些内容节点数据下一个节点的地址
typedef int SLTDateType;
typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SListNode;
尾插——尾删
不管是尾插还头插还是任意位置插入我们都需要先创建一个新节点。
尾插和尾删都需要注意一些点 用二级指针接收 因为我们这个是无头的链表在链表没有一个节点的时候我们需要创建一个节点。然后将链表的头指向这个新节点这个时候就涉及到需要修改一级结构体的一级指针。一级指针类型的变量需要修改的话就要用到二级指针。 尾插是否链表一个数据都没有这个时候我们要特殊处理一下检查链表有效性 尾删是否链表只有一个数据 检查是否有数据可以删除检查链表有效性 // 动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{SListNode* newnode (SListNode*)malloc(sizeof(SListNode));if (newnode NULL){perror(malloc fail);}newnode-data x;newnode-next NULL;return newnode;
}
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{assert(pplist);SListNode* newnode BuySListNode(x);if (*pplist NULL){*pplist newnode;return;}//找尾巴SListNode* tail *pplist;while (tail-next ! NULL)tail tail-next;tail-next newnode;
}
// 单链表的尾删
void SListPopBack(SListNode** pplist)
{assert(pplist);assert(*pplist);//有数据才能删没有数据不删至少有一个及其以上节点if ((*pplist)-next NULL){free(*pplist);*pplist NULL;}else{//找尾巴SListNode* prev NULL;SListNode* tail *pplist;while (tail-next ! NULL){prev tail;tail tail-next;}free(tail);prev-next NULL;}
} 头插——头删 头插和头删在链表中还是比较简单一个是把头节点保存起来另一个是头节点的下一个节点保存起来然后进行删除就行了。
头插注意需要检查链表有效性 头删注意这里需要检查数据个数有数据才能删除 // 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{assert(pplist);SListNode* newnode BuySListNode(x);newnode-next *pplist;*pplist newnode;
}
// 单链表头删
void SListPopFront(SListNode** pplist)
{assert(pplist);assert(*pplist);SListNode* next (*pplist)-next;free(*pplist);*pplist next;
}
查找
通过简单遍历就行了注意返回的是节点的指针 我们在外面定义的是一个链表节点的指针打印的时候按照传值的方式传递变量他会把变量的内容链表中首节点的地址拷贝过来最终返回的也是链表节点的地址 // 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{assert(plist);SListNode* cur plist;while (cur){if (cur-data x)return cur;cur cur-next;}return NULL;
}
指定位置之后删除——插入
注意写这两个接口我们首先就要想到的是检查 指定位置的有效性 还有检查 链表有效性。
代码还是很简单的这里的删除要检查是不是最后一个节点
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{assert(pos);SListNode* newnode BuySListNode(x);newnode-next pos-next;pos-next newnode;
}
// 单链表删除pos位置之后的值void SListEraseAfter(SListNode* pos)
{assert(pos);assert(pos-next);//检查是不是最后一个SListNode* next pos-next;pos-next next-next;free(next);
}
指定位置之前插入——删除指定位置
这两个接口我们需要像尾插那个样子 遍历找到指定位置前的位置然后进行插入删除同时也要注意检查链表有效性 注意 如果链表只有一个位置或者指定位置为第一个节点那删除就变成了头删可以复用原来的头删接口。尾删则没有必要我们已经遍历一遍找到尾了不需要调用尾删接口再遍历一遍了直接像尾删一样删除就行了。 // 在pos的前面插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x)
{assert(pphead);assert((!pos!(*pphead))||(pos(*pphead)))//这里我们让他都为空头插或者都不为空//我们想暴露出一个问题不允许乱位置插入 限定pos一定是有效节点if (pos *pphead){SListPushFront(pphead, x);return;}SListNode* prev *pphead;while (prev-next!pos){prev prev-next;}SListNode* newnode BuySListNode(x);newnode-next pos;prev-next newnode;
}
// 删除pos位置
void SLTErase(SListNode** pphead, SListNode* pos)
{assert(pphead);assert(*pphead);assert(pos);//这里进行检查pos必须有这个节点才能删除if (pos *pphead){SListPopFront(pphead);return;}SListNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;
}
销毁链表
这个按照遍历的同时free就行了。
注意遍历完了全部空间释放了把链表置空
void SLTDestroy(SListNode** pphead)
{assert(pphead);assert(*pphead);SListNode* cur *pphead;while (cur){SListNode* next cur-next;free(cur);cur next;}*pphead NULL;
}
打印
为了好测试写的接口是否正确我们还是写一个打印接口方便我们观察同样的循环遍历打印就行了这里不需要检查链表是否为空空链表也可以打印
// 单链表打印
void SListPrint(SListNode* plist)
{SListNode* cur plist;while (cur){printf(%d- , cur-data);cur cur-next;}printf(\n);
}
四、链表面试题 1. 删除链表中等于给定值 val 的所有结点。 203. 移除链表元素 - 力扣LeetCode 这个题我们找到与 给定值相等的节点和他的前一个节点就可以进行删除了但是我们要处理两种情况 1链表为空 2需要删除头需要循环删除因为有可能连续好几个都需要删 参考代码 struct ListNode* removeElements(struct ListNode* head, int val) {//处理链表为空if(!head) return NULL;//处理链表第一个就是该删的元素if(head-valval){while(headhead-valval){struct ListNode* nexthead-next;free(head);headnext;}}struct ListNode* curhead;struct ListNode* prevNULL;while(cur){if(cur-valval){prev-nextcur-next;free(cur);curprev-next;}else{prevcur;curcur-next;}}return head;
} 2. 反转一个单链表。 206. 反转链表 - 力扣LeetCode 这个题就是一个简单头插就行了
当然我们也可以用三个指针将链表的指向反转注意检查链表是否为空这里我们用两种方法实现两种方法任选其一都能通过 struct ListNode* reverseList(struct ListNode* head) {//头插处理// struct ListNode* newheadNULL;// while(head)// {// struct ListNode* nexthead-next;// head-nextnewhead;// newheadhead;// headnext;// }// return newhead;//直接反转if(!head)return head;struct ListNode* n1NULL,*n2head,*n3head-next;while(n2){n2-nextn1;n1n2;n2n3;if(n3)n3n3-next; }return n1;
} 3. 给定一个带有头结点 head 的非空单链表返回链表的中间结点。如果有两个中间结点则返回第二个中间结点。 876. 链表的中间结点 - 力扣LeetCode 这个题是一个标准的 快慢指针 值得注意的是我们判断条件是快指针为NULL或者快指针的下一个节点为NULL他们在循环中判断的先后为先判断自己再判断下一个因为先判断下一个的话有可能出现野指针问题。 struct ListNode* middleNode(struct ListNode* head) {//快慢指针法struct ListNode* fasthead;struct ListNode* slowhead;while(fastfast-next){fastfast-next-next;slowslow-next;}return slow;
} 4. 输入一个链表输出该链表中倒数第k个结点。 面试题 02.02. 返回倒数第 k 个节点 - 力扣LeetCode 这个题也是一个经典的双指针可以让快指针先走k次然后快慢指针同时走每次走一下 int kthToLast(struct ListNode* head, int k){struct ListNode* fasthead;struct ListNode* slowhead;while(k--)fastfast-next;while(fast){fastfast-next;slowslow-next;}return slow-val;
} 5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的。 21. 合并两个有序链表 - 力扣LeetCode 这个题就要用到并归和尾插了选择小的尾插到新链表里面这个尾插是移动他的链表节点到我们新的链表里面。 需要注意的是1.需要处理空链表情况一个为空或者两个为空 2.处理头节点 struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {//处理为空的情况 if(!list1)return list2;if(!list2)return list1;struct ListNode* headNULL;struct ListNode* tailNULL;while(list1list2){if(list1-vallist2-val){struct ListNode* nextlist1-next;if(headNULL)//处理头节点headtaillist1;else{tail-nextlist1;tailtail-next;tail-nextNULL;//这个可以不处理后面剩余节点的尾巴也一定是NULL}list1next;}else{struct ListNode*nextlist2-next;if(headNULL)//处理头节点headtaillist2;else{tail-nextlist2;tailtail-next;tail-nextNULL;}list2next;}}if(list1NULL)//处理剩余未插入的节点tail-nextlist2;elsetail-nextlist1;return head;
} 6. 编写代码以给定值 x 为基准将链表分割成两部分所有小于 x 的结点排在大于或等于 x 的结 点之前 。 链表分割_牛客题霸_牛客网 (nowcoder.com) 这个题呢我们用把链表分成两条小于给定值的在一条大于给定值的在一条然后在连接起来就行了。 注意这里我们要用到 带头的单链表无头的单链表会有很多问题要处理。我们还需要将链表移动后 置空不然后面连接起来可能会出现很多问题 class Partition {public:ListNode* partition(ListNode* pHead, int x) {ListNode* head1, *tail1, *head2, *tail2;head1 tail1 (ListNode*)malloc(sizeof(ListNode));//第一条链表head2 tail2 (ListNode*)malloc(sizeof(ListNode));//第二条链表tail1-next tail2-next NULL;while (pHead) {if (pHead-val x) {ListNode* next pHead-next;tail1-next pHead;tail1 tail1-next;tail1-next NULL;pHead next;} else {ListNode* next pHead-next;tail2-next pHead;tail2 tail2-next;tail2-next NULL;pHead next;}}tail1-nexthead2-next;ListNode* rehead1-next;free(head2);free(head1);return re;}
}; 7. 链表的回文结构。OJ链接 这个题我们需要找到中间节点先遍历找出节点个数即可找到然后翻转一半节点到创建的另一个链表当中然后进行比对即可得到是否为回文结构 class PalindromeList {
public:bool chkPalindrome(ListNode* A) {if(!A) return true;int count0;ListNode* curA;while(cur){curcur-next;count;}count(count1)/2;int icount;ListNode*headNULL;while(i--){ListNode*nextA-next;A-nexthead;headA;Anext;}while(headA){if(head-val!A-val)return false;headhead-next;AA-next;}return true;}
}; 8. 输入两个链表找出它们的第一个公共结点。 160. 相交链表 - 力扣LeetCode 这个题我们可以首先想到暴力解法先在定一条链表中的某个节点然后再另一个链表中找该节点如果找到了有返回该节点不过这样的解法时间复杂度太高了
第二种方法是我们先遍历各自链表找出其中个数先让长的那一条链表先走他们的节点个数差然后两条链表同时遍历找出相交节点
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {int cnt10,cnt20;struct ListNode* cur1headA;while(cur1){cur1cur1-next;cnt1;}struct ListNode* cur2headB;while(cur2){cur2cur2-next;cnt2;}if(cur2!cur1)//如果链表到最后都不相等说明不相交没有交点return NULL;//假定A比B长struct ListNode* haheadA;struct ListNode* hbheadB;if(cnt1cnt2){haheadB;hbheadA;}int cntabs(cnt1-cnt2);while(cnt--)//让长的先走个数差haha-next;while(ha)//两条链表同时遍历{if(hahb)//注意两个节点相等不是节点值相等 return ha;haha-next;hbhb-next;}return NULL;
} 9.给定一个链表判断链表中是否有环。141. 环形链表 - 力扣LeetCode 这是一个经典快慢指针
bool hasCycle(struct ListNode *head) {struct ListNode* fasthead;struct ListNode* slowhead;while(fastfast-next){fastfast-next-next;slowslow-next;if(fastslow)return true;}return false;
} 10.给定一个链表返回链表开始入环的第一个结点。 如果链表无环则返回 NULL 142. 环形链表 II - 力扣LeetCode 这个题需要我么用到简单的数学知识 struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* fasthead;struct ListNode* slowhead;while(fastfast-next){fastfast-next-next;slowslow-next;if(fastslow){struct ListNode* curhead;while(cur!fast){curcur-next;fastfast-next;}return cur;}}return NULL;
} 11. 给定一个链表每个结点包含一个额外增加的随机指针该指针可以指向链表中的任何结点或空结点。 要求返回这个链表的深度拷贝。 138. 随机链表的复制 - 力扣LeetCode 这个题我们可以用这个方法 在原链表中每个节点都复制一个节点插入在自己的后面
然后进行random处理如果原节点的random存在则新节点的random指向原节点的random的下一个。最后将两条链表分离即可。 struct Node* copyRandomList(struct Node* head) {if(!head) return NULL;struct Node* curhead;while(cur){struct Node* newnode(struct Node*)malloc(sizeof(struct Node));newnode-nextcur-next;newnode-valcur-val;newnode-randomNULL;cur-nextnewnode;curnewnode-next;}curhead;while(cur){struct Node* newcur-next;if(cur-random)new-randomcur-random-next;curnew-next;}curhead;struct Node* newheadcur-next;struct Node* tailcur-next;while(cur){cur-nexttail-next;curcur-next;if(cur)tail-nextcur-next;tailtail-next;}return newhead;
} 五、总体代码
SList.h
#pragma once
#includestdio.h
#includeassert.h
#includestdlib.h
// slist.h
typedef int SLTDateType;
typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SListNode;// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置
void SListEraseAfter(SListNode* pos);// 在pos的前面插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x);
// 删除pos位置
void SLTErase(SListNode** pphead, SListNode* pos);
void SLTDestroy(SListNode** pphead);SList.h
#define _CRT_SECURE_NO_WARNINGS 1
#includeSList.h// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{SListNode* newnode (SListNode*)malloc(sizeof(SListNode));if (newnode NULL){perror(malloc fail);}newnode-data x;newnode-next NULL;return newnode;
}
// 单链表打印
void SListPrint(SListNode* plist)
{assert(plist);SListNode* cur plist;while (cur){printf(%d- , cur-data);cur cur-next;}printf(\n);
}
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{assert(pplist);SListNode* newnode BuySListNode(x);if (*pplist NULL){*pplist newnode;return;}//找尾巴SListNode* tail *pplist;while (tail-next ! NULL)tail tail-next;tail-next newnode;
}
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{assert(pplist);SListNode* newnode BuySListNode(x);newnode-next *pplist;*pplist newnode;
}
// 单链表的尾删
void SListPopBack(SListNode** pplist)
{assert(pplist);assert(*pplist);//有数据才能删没有数据不删if ((*pplist)-next NULL){free(*pplist);*pplist NULL;}else{//找尾巴SListNode* prev NULL;SListNode* tail *pplist;while (tail-next ! NULL){prev tail;tail tail-next;}free(tail);prev-next NULL;}
}
// 单链表头删
void SListPopFront(SListNode** pplist)
{assert(pplist);assert(*pplist);SListNode* next (*pplist)-next;free(*pplist);*pplist next;
}
// 单链表查找
//plist是一个变量保存的是地址传的时候也是地址传过去就是将变量里面的地址拷贝一份传过去了
SListNode* SListFind(SListNode* plist, SLTDateType x)
{assert(plist);SListNode* cur plist;while (cur){if (cur-data x)return cur;cur cur-next;}return NULL;
}
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入
void SListInsertAfter(SListNode* pos, SLTDateType x)
{assert(pos);SListNode* newnode BuySListNode(x);newnode-next pos-next;pos-next newnode;
}
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置
void SListEraseAfter(SListNode* pos)
{assert(pos);assert(pos-next);//检查是不是最后一个SListNode* next pos-next;pos-next next-next;free(next);
}// 在pos的前面插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x)
{assert(pphead);assert(*pphead);//这里没有检查pos是否为NULL我认为在最后一个节点之后插入也是可以的if (pos *pphead){SListPushFront(pphead, x);return;}SListNode* prev *pphead;while (prev-next!pos){prev prev-next;}SListNode* newnode BuySListNode(x);newnode-next pos;prev-next newnode;
}
// 删除pos位置
void SLTErase(SListNode** pphead, SListNode* pos)
{assert(pphead);assert(*pphead);assert(pos);//这里进行检查pos必须有这个节点才能删除if (pos *pphead){SListPopFront(pphead);return;}SListNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;
}
void SLTDestroy(SListNode** pphead)
{assert(pphead);assert(*pphead);SListNode* cur *pphead;while (cur){SListNode* next cur-next;free(cur);cur next;}*pphead NULL;
}
Test.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeSList.h
void test1()
{SListNode* SL NULL;SListPushBack(SL, 1);SListPushBack(SL, 2);SListPushBack(SL, 3);SListPushBack(SL, 4);SListPushBack(SL, 5);SListPrint(SL);SListPushFront(SL, 6);SListPushFront(SL, 7);SListPushFront(SL, 8);SListPushFront(SL, 9);SListPushFront(SL, 10);SListPushFront(SL, 99);SListPushFront(SL, 88);SListPushFront(SL, 77);SListPrint(SL);SListPopBack(SL);SListPopBack(SL);SListPopBack(SL);SListPopBack(SL);SListPrint(SL);SListPopFront(SL);SListPopFront(SL);SListPopFront(SL);SListPrint(SL);SListInsertAfter(SListFind(SL, 1), 99);SListInsertAfter(SListFind(SL, 10), 99);SListPrint(SL);SListEraseAfter(SListFind(SL, 1));SListEraseAfter(SListFind(SL, 10));//printf(%d\n, SListFind(SL, 1)-data);SListPrint(SL);SLTInsert(SL, SListFind(SL, 10), 99);SLTInsert(SL, NULL, 99);SListPrint(SL);SLTErase(SL, SListFind(SL, 99));SLTErase(SL, SListFind(SL, 99));SListPrint(SL);SLTDestroy(SL);}
int main()
{test1();return 0;
}
