12306网站是是阿里巴巴做的吗,专业建网站设计公司,网站识别手机电脑自动跳转,东莞网站建设套餐那么上一题我们已经知道了双指针的变法以及拓展的用法#xff0c;那么这里我们直接难度升级。
想回去复习的这里放个链接#xff1a;链表的面试题8之环形链表-CSDN博客
题目链接#xff1a;142. 环形链表 II - 力扣#xff08;LeetCode#xff09; 我们来看这道题目主要…那么上一题我们已经知道了双指针的变法以及拓展的用法那么这里我们直接难度升级。
想回去复习的这里放个链接链表的面试题8之环形链表-CSDN博客
题目链接142. 环形链表 II - 力扣LeetCode 我们来看这道题目主要想让我们干什么上一题是让我们去判断是否为环形链表而这一题是直接告诉你这就是一个环形链表让你自己去探寻环形链表各节点的关系用地址来判断这个节点是否是第一个成环的节点。
当然这一题还是用双指针的解法至于为什么很简单单指针解决不了这个问题呗。我们上一题探讨过快慢指针的步调的大小涉及快慢指针的算法题中通常习惯使用快指针每次走两步慢指针走一步的方式。
这里我们需要判断的难点是什么
我们之前用到的快慢指针都是通过他们的距离差让这两个指针相遇来得出这个是环形链表但是这里我们相遇的点万一不是第一个点呢那么我们的判断不就成了无效判定了吗所以我们笃定一点这道题像上一道题那样的关系判断是不可取的我们应该找其他的关系使得让两个节点一定在第一个成环的节点相遇。
那我们直接来画图看一下 这里我们设从头节点到入环的第一个节点的距离为a设环长为c。
再设相遇的时候慢指针走了b步那么这里快指针就走了2b步。
再设快指针比慢指针多走了k圈环那么我们就能得到2b-bkc即bkc。
再看我们的慢指针从头节点开始到相遇点走了b-a步也就是kc-a步。
这也就是说从相遇点开始再走a步就会到达我们的入环点。
为什么
因为环长就是c看图中的箭头一根箭头代表一个长度。所以再走a步也就是说(kc-aa)kc步
也就是在入环口处。那么哪里还有a步的地方呢
我再往图里一看那就是头节点处所以我如果让指针从头节点和相遇点处分别开始移动那么两个人步伐都为1的情况下肯定会在入环口处相遇。
结论就是让一个指针从链表起始位置开始遍历链表同时让一个指针从判环时相遇点的位置开始绕环运行两个指针都是每次均走一步最终肯定会在入口点的位置相遇。
但要注意一点指针从相遇点开始移动 a 步后恰好走到入环口但在这个过程中可能会多次经过入环口。 因为环长和入环前的长度可能会有误差。
struct ListNode* detectCycle(struct ListNode* head) {struct ListNode* slow head;struct ListNode* fast head;while (fast fast-next) {slow slow-next;fast fast-next-next;if (fast slow) { // 相遇while (slow ! head) { // 再走 a 步slow slow-next;head head-next;}return slow;}}return NULL;
}
这里把代码贴一下整个思路是非常清晰的效率也非常高。
时间复杂度O(n)其中 n 为链表的长度。 空间复杂度O(1)仅用到若干额外变量。
这里再带大家注意两点推导设条件的前提1.慢指针在进入环之前快指针就已经在环内至少走了n圈而n至少为1。因为快指针至少要走一圈才能与后进入的慢指针相遇。
2.慢指针进环之后快指针肯定会在慢指针走一圈之内追上慢指针 因为慢指针进环后快慢指针之间的距离最多就是环的长度而两个指针在移动时每次它们至今的距离都缩减一步因此在慢指针移动一圈之前快指针肯定是可以追上慢指针的。
好了这道题就讲到这里
如果你觉得对你有帮助可以点赞关注加收藏感谢您的阅读我们下一篇文章再见。
一步步来总会学会的首先要懂思路才能有东西写。
