网站建设技术人员工作总结,网站推广去哪家比较好,公司实验室设计,网站店招用什么软件做的#x1f4af;#x1f4af;#x1f4af;#x1f4af; 本篇主要研究的是链表带环问题#xff0c;快慢指针的应用#xff0c;分析不同解法对带环链表的处理#xff0c;梳理完本篇你将对链表的理解更加透彻Ⅰ.研究链表带环问题Ⅱ.扩展带环问题1.为什么慢指针和快指针一定会相…
本篇主要研究的是链表带环问题快慢指针的应用分析不同解法对带环链表的处理梳理完本篇你将对链表的理解更加透彻Ⅰ.研究链表带环问题Ⅱ.扩展带环问题1.为什么慢指针和快指针一定会相遇2.快指针一次走3步4步…n步可以吗3.慢指针走的距离和快指针走的距离Ⅲ.总结归纳结论带环定理Ⅳ.带环链表真题方法1利用带环定理方法2转换为相交链表问题Ⅰ.研究链表带环问题
链表带环是什么意思呢 就是一个链表有一个结点指向了前面结点导致又链接回来的问题 如果进行遍历就会变成死循环
那么如何判断一个链表是否带环呢 链表带环问题Ⅰ
思路 我们可以利用快慢指针慢指针走一步快指针走两步当快指针进入环中时慢指针肯定还在外面当慢指针进环时快指针可能已经走了好几圈但一旦两个指针进环后肯定会相遇我们可以将带环问题转换为相遇问题也就是小学经常看到的小明先跑50速度为5m/s小亮后跑速度为10m/s,问何时相遇。
我们只要判断它们是否相遇了就能确定是否带环因为如果没有带环的话那就不可能相遇快指针肯定先走出去。 快慢指针即慢指针一次走一步快指针一次走两步两个指针从链表其实位置开始运行 如果链表带环则一定会在环中相遇否则快指针率先走到链表的末尾。 bool hasCycle(struct ListNode *head){struct ListNode*fast,*slow;fastslowhead;//快慢指针都从开头开始走while(fastfast-next){slowslow-next;fastfast-next-next;if(fastslow)//如果慢指针等于快指针则一定在环里return true;}return false;//否则就不在环里
}Ⅱ.扩展带环问题
1.为什么慢指针和快指针一定会相遇
假设链表带环快慢指针同时走快指针先入环慢指针后入环当慢指针刚入环时有可能与快指针相遇也有可能与快指针相差很远但这不是问题关键的关键是它们两都在环里并且快指针每次走两步慢指针每次走1步而它们每次走一步时它们之间的距离就减少1每走一步快指针就追上一步所以它们之间的距离在不断的缩小最后肯定能追上。
并且不会出现套圈的现象因为两个结点之间最小的距离也就是1了每次缩小1最后要么重合要么还是重合不可能从头上跳过去的。
还有慢指针在慢指针走到一圈之前快指针肯定是可以追得上慢指针的即相遇 慢指针刚入环时与快指针最远距离可能为一个环距离吧但想一想当慢指针走了一环距离时快指针走了多少快指针走的是慢指针的2倍呀那肯定是2圈了都慢指针走1圈快指针都要走两圈了这里面肯定追上慢指针了。
2.快指针一次走3步4步…n步可以吗
其实这种本质上看的是相对位移量只要我们算出相对位移量就可以判断了。上面快指针每次走2步慢指针每次走1步它们每次走一步都会缩小1距离而因为1就是最小距离单位所以最后肯定会相遇。 但如果一次走三步就不一定了 假设快慢指针都入环后它们之间的距离为N 快指针每次走3步慢指针每次走1步那它们每次走快指针都会缩小2个距离那它们之间的距离就变成了N-2再走就变成N-4N-6……这里就涉及N是奇数还是偶数了当N是偶数时那么最后它们是可以相遇的如果是奇数那这圈是不会相遇的不过最后走完快慢指针之间的距离就变成-1了也就是这个环的周长减1距离这又要取决于环的周长是偶数还是奇数了……。
如果快指针每次走4步道理也是一样的在快慢指针都入环后假设它们的距离为N 则每次距离都会缩小3则最好是否相遇取决于N是否是3的倍数了。
3.慢指针走的距离和快指针走的距离 你想一想快指针和慢指针在相遇前总共走了多远距离呢 快慢指针是同时从开始位置走的快指针走的快先入环慢指针走的慢后入环。 前面我们知道fast在slow走满一圈之前追上所以slow不可能走过一圈的所以慢指针走的总距离为LM
而快指针就不一定了快指针走的快先入环谁知道它在环里走了多少圈了都而且走的圈数越多说明这个环越小 所以快指针走的总距离为 LMnC (n至少为1)* n为走过的圈数
Ⅲ.总结归纳
因为快慢指针之间存在着关系所以我们可以列出一个表达式也就是快指针走的距离是慢指针走的距离的2倍 2*(LM)LMn*C
所以Ln*C-M 当最好情况下n1时LC-M L是什么L就是开始点到入口点的距离 C-M是什么C-M就是相遇点到入口点的距离。
也就是一个指针从链表的起始位置开始运行一个指针从相遇点位置绕环每次都走一步两个指针最终会在入口点的位置相遇 结论带环定理
让一个指针从链表的起始位置开始遍历同时让一个指针从带环的相遇点位置开始遍历两个指针都是每次走一步最终一定会在入环处相遇
Ⅳ.带环链表真题
给定一个链表返回链表开始入环的第一个结点如果链表无环则返回NULL 《链表带环问题Ⅱ》 要求判断是否有环如果有请返回入环的第一个结点。
方法1利用带环定理
这就是我上面两个例子的结合第一步判断是否有环第二步利用上面的定理在有环的链表中从开始位置和相遇点同时出发将会在入环点相遇。
struct ListNode *detectCycle(struct ListNode *head)
{//首先判断是否有环struct ListNode *fast,*slow;fastslowhead;while(fastfast-next){slowslow-next;fastfast-next-next;if(fastslow){//fast与slow现在就是相遇点//这时从开始点和相遇点同时走当相等时就是入环点while(head!slow)//如果不相同就一直走{headhead-next;slowslow-next;}return head;//当跳出来时就是入环点}}return NULL;}方法2转换为相交链表问题
还有一种方法可以快速解决这个问题我们可以将相遇点与后面那个结点断开 那从断开的结点开始是不是就相当于一个链表了那这道题目就转变成了相交链表的问题了求两个链表相交的结点问题我在上一篇博客中有写过这种方法。 如果求两个相交链表的结点呢 其实很简单 第一步求出两个链表的长度 第二步让长度较长的链表先走长度差步 第三两个链表一起走并进行比较当两个链表的结点相同时就是相交结点。 struct ListNode *detectCycle(struct ListNode *head){//首先要找到相遇点才能断开它struct ListNode*fast,*slow;fastslowhead;while(fastfast-next){slowslow-next;fastfast-next-next;if(fastslow){//fast和slow现在就是相遇点断开它和下一个结点并保存下一个结点的地址struct ListNode*newnodeslow-next;slow-nextNULL;//newnode就是新链表的头指针啦//开始求两个链表长度int len10,len20;struct ListNode*tail1head,*tail2newnode;while(tail1)//计算链表1的长度{tail1tail1-next;len1;}while(tail2)//计算链表2的长度{tail2tail2-next;len2;}//两个链表长度是求出来来了但不知道哪个是长链表哪个是短链表呀所以还需要讨论下int gapabs(len1-len2);struct ListNode*longlisthead,*shortlistnewnode;if(len1len2){longlistnewnode;shortlisthead;}//让长的链表先走长度差while(gap--){longlistlonglist-next;}//然后两个链表再一起走比较相同的时就是相交结点while(longlist!shortlist){longlistlonglist-next;shortlistshortlist-next;}return longlist;//最后返回相交结点}} return NULL;
}
