网站建设数据库设计,河南网站备案所需资料,wordpress 别名插件,推广赚钱的软件排行生活就像一盒巧克力#xff0c;你永远不知道你会得到什么。——《阿甘正传》目前自己粗略的学完数据结构#xff0c;正在开始刷算法题目。个人觉得算法是一个积累#xff0c;循序渐进的的过程#xff0c;需要不断加量#xff0c;进而达到所谓的质。链表作为数据结构一个重…生活就像一盒巧克力你永远不知道你会得到什么。——《阿甘正传》目前自己粗略的学完数据结构正在开始刷算法题目。个人觉得算法是一个积累循序渐进的的过程需要不断加量进而达到所谓的质。链表作为数据结构一个重要的分支。我们没有理由不学好它并且没有理由不刷一些链表的算法题。所以今天想和大家讲解一下链表有无存在环的经典题目并且由这道题目本身知识点发散开来进而来解决一道有无环的进阶题目。看完这一篇文章你的收获一定会非常之大。看完理解其中的原理之后你只想说秒牛我靠还能这样·······甚至你会直接关注我给我点个赞。目录一.判断链表是否有环1.双指针作用(铺垫)2.结论环形链表的环一定在末尾末尾没有NULL3.具体步骤思路4.详细代码二.链表中环的入口节点1.思路2.两个结论4.详细代码一.判断链表是否有环先把题目给到大家大家可以浏览一下1.双指针作用(铺垫)双指针的作用由于单向链表(如上图)的每一个指针只能从头往后扫描并不能从后往前的这一个局限性。所以我们在解决单向链表的题目上引入双指针。双指针指的是在遍历对象的过程中不是普通的使用单个指针进行访问而是使用两个指针特殊情况甚至可以多个两个指针或是同方向访问两个链表或是同方向访问一个链表快慢指针、或是相反方向扫描对撞指针从而建立一种手段让这种手段为我们的目的服务。2.结论环形链表的环一定在末尾末尾没有NULL证明看上图在环20-4中没有任何一个节点可以指出环它们只能在环内不断循环链表不像二叉树每个节点只有一个val值和一个next指针也就是说一个节点只能有一个指针指向下一个节点不能有两个指针。因此环后面不可能还有一条尾巴。如果是普通链表末尾一定有NULL(第一个图)那我们可以根据链表中是否有NULL判断是不是有环。3.具体步骤思路step 1设置快慢两个指针初始都指向链表头。step 2遍历链表快指针每次走两步慢指针每次走一步。step 3如果快指针到了链表末尾说明没有环因为它每次走两步所以要验证连续两步是否为NULL。step 4如果链表有环那快慢双指针会在环内循环因为快指针每次走两步因此快指针会在环内追到慢指针二者相遇就代表有环。·对于step4的进一步解释(个人理解)我们可以这样想这个快指针一次是走两步然后慢指针一次走一步两指针距离会拉大每循环一次两个指针的距离就会1我们假设在遇到环的那一刻他们之间的距离就是n这时候慢指针在后面快指针在这个环做周期性走动慢指针就一步一步的跟上这个快指针也就是这个n以减1的速度一直在靠近0直到n0这个时候快慢指针就相遇。就能够判断链表有环。画图解释看下图快指针走两步慢指针走一步最后相遇。一步一步分析。4.详细代码前面都是理论接下来用代码实现#include stdbool.hstruct ListNode {int val;struct ListNode *next;};//定义一个结点
bool hasCycle(struct ListNode* head )/返回类型是bool
{struct ListNode*fasthead;struct ListNode*slowhead;while(fast!NULLfast-next!NULL){fastfast-next-next;//快指针走两步slowslow-next;//慢指针走一步if(slowfast)//如果相遇则有环{return true;}}return false;
}二.链表中环的入口节点在上一道题目的基础上我们再来搞定这一道进阶题目1.思路 设置快慢指针都从链表头出发快指针每次走两步慢指针一次走一步假如有环一定相遇于环中某点(结论一)。接着让两个指针分别从相遇点和链表头出发两者都改为每次走一步最终相遇于环入口(结论二)。以下是两个结论证明2.两个结论结论一设置快慢指针假如有环他们最后一定相遇。证明设置快慢指针fast和slowfast每次走两步slow每次走一步。假如有环两者一定会相遇因为slow一旦进环可看作fast在后面追赶slow的过程每次两者都接近一步最后一定能追上。也即第一道题的结论。结论二两个指针分别从链表头和相遇点继续出发每次走一步最后一定相遇与环入口。证明设链表头到环入口长度为--a环入口到相遇点长度为--b相遇点到环入口长度为--c则相遇时快指针路程a(bc)kb k1 其中bc为环的长度k为绕环的圈数k1,即最少一圈不能是0圈不然和慢指针走的一样长矛盾。慢指针路程ab快指针走的路程是慢指针的两倍所以ab*2a(bc)kb化简可得a(k-1)(bc)c 这个式子的意思是 链表头到环入口的距离相遇点到环入口的距离k-1圈环长度。其中k1,所以k-10圈。所以两个指针分别从链表头和相遇点出发最后一定相遇于环入口。4.详细代码前面都是理论接下来用代码(C)实现class Solution {
public:ListNode* EntryNodeOfLoop(ListNode* pHead) {ListNode*fastpHead;ListNode*slowpHead;while(fast!nullptrfast-next!nullptr){fastfast-next-next;slowslow-next;if(fastslow)break;}if(!fast||!fast-next)return nullptr;slowpHead;while(slow!fast){fastfast-next;slowslow-next;}return slow;}
};以上是两道很经典的题目就讲解到这里。哦对了刚刚在构思这篇文章的过程中突然想到今天是情人节然后然后脑子里突然想起正在看这篇文章的你可能你还没对象所以呢哈哈哈下一篇文章要讲解关于C中new这类知识点最后new一个自己想要的理想对象致敬在座的每个人。关记得关注我下一篇今晚就发。
