做外贸是用什么网站做,wordpress做登陆页面,免费如何做网页或网站,网站建设教案前言 上一节我们学习了链表的概念以及链表的实现#xff0c;那么本节我们就来了解一下链表具体有什么用#xff0c;可以解决哪些实质性的问题#xff0c;我们借用习题来加强对链表的理解#xff0c;那么废话不多说#xff0c;我们正式进入今天的学习
单链表相关经典算法O…前言 上一节我们学习了链表的概念以及链表的实现那么本节我们就来了解一下链表具体有什么用可以解决哪些实质性的问题我们借用习题来加强对链表的理解那么废话不多说我们正式进入今天的学习
单链表相关经典算法OJ题1移除链表元素
https://leetcode.cn/problems/remove-linked-list-elements/description/
题目详情 题解
思路一
要想解决这个题目我们首先需要创建一个名为 pcur 的变量用来遍历整个链表找到与 val 相等的值当我们找到了值为 val 的节点我们不能直接释放掉这个节点这样会导致后面的数据无法被找到我们此时还需要定义一个变量 prev 让 prev 一只指向 pcur 的前一个节点。当我们找到值为 val 的节点该节点此时被 pcur 指向我们需要用 pcur-next 来找到它的下一个节点我们再次创建一个变量 next 把 pcur-next 存入 next 变量中并且把这个节点与 prev 所指向的节点连接起来再释放掉 pcur 此时就完成了移除链表元素的功能
思路二
我们重新创建一个链表 newHead 和新链表的尾节点指针 newTail 我们在原链表中进行遍历将所有值不为 val 的节点尾插至新链表中去。
我们首先需要创建一个名为 pcur 的变量用来遍历整个链表若找到的值不为 val 则直接尾插到新链表的 newTail 后面去同时让 newTail 指针向后挪动而 newHead 指针一直保持不变
假设我们用思路二来解决问题
我们想要完成该函数的功能首先我们需要往函数中传入两个变量
1.链表的头节点 struct ListNode* head
2. value 的取值 int val
在开始插入的时候我们还需要判断链表当前的情况到底是为空还是不为空
如果链表为空的话要将 newHead 和 newTail 都赋予 pcur此时头节点等于尾节点
如果链表不为空newTail-next 要等于 pcur 而此时 newTail 变量要等于 newTail-next
排查
此时我们再来考虑一下特殊情况若是要移除的数据是链表的尾节点。
我们遍历到原链表的倒数第二个数据的时候倒数第二个数据的 next 指针指向了尾节点即使不插入最后一个元素到新链表中倒数第二个节点仍然可以通过它自身的 next 指针找到原链表的尾节点此时就会导致代码出现错误原链表中的尾节点还是被插入到了新链表中去了
那么我们怎么才能在这种情况下不带上最后一个节点呢
当我们找到并且尾插了倒数第二个节点的时候我们此时把它的 next 指针赋予空指针 NULL这样他就找不到原链表的最后一个节点了
此时我们还要考虑到一个问题因为题目中说了列表的节点数目可以为0若链表的节点个数为0时此时我们就不能把 newTail 中的 next 指针设置为空指针这样就会造成对空指针进行解引用的问题
那么根据上述的逻辑以及注意事项的规避我们可以写出代码如下
typedef struct ListNode ListNode;struct ListNode* removeElements(struct ListNode* head, int val)
{//创建一个新链表ListNode * newHead, * newTail;newHead newTail NULL;//遍历原链表ListNode* pcur head;while (pcur){//找值不为 val 的节点然后尾插到新链表中if (pcur-val ! val){//链表为空if (newHead NULL){newHead newTail pcur;}//链表不为空else{newTail-next pcur;newTail newTail-next;}}pcur pcur-next;}if (newTail)newTail-next NULL;return newHead;
}
我们在Leetcode官网检测一下结果是否正确 代码成功的解决问题该题目完成
单链表相关经典算法OJ题2反转链表
题目详情 题解
思路一
我们可以创建一个新的链表我们逐一的遍历原链表让里面的每一个节点按顺序头插到新链表之中去当遍历结束后此时我们拿到的新链表就是反转了以后的链表
思路二
我们先创建三个变量分别为 n1 n2 n3。我们先让 n1 指向空指针让 n2 指向链表的头节点让 n3 指向 n2 的下一个节点
要完成链表的反转我们需要按以下步骤操作 1.先让 n2 的 next 指针不再指向 n3 而是让它指向 n1 n1 初始的情况下为空指针 2.我们再让 n1 指向 n2 让 n3 指向它的下一个节点 3.我们重复以上步骤让 n2 的 next 指针不再指向 n3 而是让它指向 n1 4.一直重复以上步骤当 n2 和 n3 已经找不到节点了此时我们可以跳出循环现在 n1 指向的位置就是反转以后链表的头节点
5.因为原题目说了链表可以为空所以我们还需要判断是否为空
此时我们来尝试实现代码
typedef struct ListNode ListNode;struct ListNode* reverseList(struct ListNode* head)
{//判空if (head NULL){return head;}//创建三个指针ListNode* n1, * n2, * n3;n1 NULL, n2 head, n3 n2-next;while (n2){n2-next n1;n1 n2;n2 n3;if (n3)n3 n3-next;}return n1;
}提醒最后一次让 n3 n3-next 的代码不能够执行因为此时 n3 已经是空指针了不能对空指针进行解引用所以我们需要对 n3 加以判断
我们现在在Leetcode的官网运行一下代码 代码成功的解决问题该题目完成
单链表相关经典算法OJ题3链表的中间结点
题目 题解
思路一
我们可以遍历全链表定义一个变量 count 用来计算遍历的节点数当遍历结束后直接返回 count / 2节点则该节点就是链表的中间节点
思路二快慢指针
我们首先分为奇数个和偶数个两种情况
我们先定义两个变量一个叫做 slow 指针一个叫做 fast 指针我们让 slow 指针每次走一步fast 指针一次走两步2slow fast
1.若链表的节点数为奇数个当 fast-next 指针指向到 NULL 指针时此时 slow 指针刚好指向链表的中间节点
2.若链表的节点数为偶数个当 fast 指针指向到 NULL 指针时此时 slow 指针刚好指向链表的中间节点
有了这个思想以后我们试着写出代码
typedef struct ListNode ListNode;struct ListNode* middleNode(struct ListNode* head)
{//创建快慢指针ListNode* slow head;ListNode* slow head;while (fast fast-next){slow slow-next;fast fast-next-next;}//此时slow刚好指向中间节点return slow;}
我们在 Leetcode 的官网运行一下代码看看结果 代码成功的解决问题该题目完成
结尾
本节我们了解了链表在题目中的应用下一节同样给大家细细讲解链表在题目中的应用帮助大家更好的理解链表那么本节的内容就到此为止了谢谢您的浏览
