关注、星标下方公众号,和你一起成长
作者 | 梁唐
出品 | 公众号:Coder梁(ID:Coder_LT)
(资料图片仅供参考)
大家好,我是梁唐。
今天我们来看一道非常非常经典的算法题,它曾经是微软的著名面试题之一,也是《编程之美》一书中的经典例题。它同样也被收录进了LeetCode当中。
给定一个链表的头节点 head
,返回链表开始入环的第一个节点。 如果链表无环,则返回 null
。
如果链表中有某个节点,可以通过连续跟踪 next
指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos
来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos
是 -1
,则在该链表中没有环。注意:pos
不作为参数进行传递,仅仅是为了标识链表的实际情况。
不允许修改链表。
如果只是为了通过,这题其实很简单,我们只需要使用一个数据结构存储下所有遍历经过的节点。只要遇到了之前出现过的节点,那么就返回,否则则继续遍历,直到遍历结束为止。
最坏的情况当中,我们需要额外将链表中的数据都再存储一遍,因此消耗的空间复杂度是 。
classSolution{public:ListNode*detectCycle(ListNode*head){setst;autopt=head;while(pt!=nullptr){if(st.count(pt))returnpt;st.insert(pt);pt=pt->next;}returnnullptr;}};
显然,仅仅是这样的难度是进不了微软的面试题库的。所以我们还要更进一步,加大难度:如果将空间复杂度限制在 呢?
老实说,在没有额外信息的前提下想要直接一步到位想出正解是比较困难的。可能很多算法老手也不一定能马上反应过来。
所以这里我们先退一步,稍微降低一点难度。相信大家也注意到了,本题的名字是环形链表II。自然也有环形链表I,环形链表I的题面和本题完全一样。只不过我们不需要返回环的起始位置,只需要判断是否有环存在。我们可以先想出在 空间复杂度下判断是否有环的方法,再进一步构思出如何找到环开头的位置,这样相对来说会更加自然。
只能使用 的空间复杂度意味着我们不能再记录每一个遍历过的节点,而需要使用其他的方法来判断。我们可以从有环的链表与无环链表的差异来入手。
比较容易想到,如果链表有环的话,那么当我们遍历它的时候会陷入无限循环。但是由于我们事先并不知道链表中节点的个数,所以也就没办法直接根据遍历的节点的个数来判断是否陷入了无限循环。
我们可以用一个非常巧妙的思路来解决这个问题,我们可以把链表中的环想象成学校的操场,遍历节点的指针想象成跑步的学生。如果我们只有一个学生很难判断,但如果我们有两个学生呢?一个跑得快一个跑得慢,那么只要他们一直跑下去,他们一定会某一刻相遇。反之,如果不存在环,他们也就没办法相遇。
我们从这点入手,创建两个指针,一个指针每次移动两个节点,一个指针每次移动一个。如果中途快的指针和慢的指针相等, 那么说明链表中一定有环,快的指针开始跑圈了。
classSolution{public:boolhasCycle(ListNode*head){autofast=head,slow=head;while(fast!=nullptr){fast=fast->next;if(fast==nullptr)returnfalse;fast=fast->next;slow=slow->next;if(fast==slow)returntrue;}returnfalse;}};
解决了判断是否有环的问题之后,剩下的就是判断环起始的位置了。
怎么判断呢?干想肯定是没用的,我们还是要结合问题来分析。我们用一张图画一下快慢指针相遇时的情况:
一段时间之后快慢指针相遇在了紫色点的位置,其中慢指针移动的距离就是红色和绿色的部分,即a+b
。我们再来看快指针,它移动的范围是红色区域,并且还绕着环走了n
圈到了紫色。所以它的移动轨迹是a + n(b+c)
。但同时它的移动速度又是慢指针的两倍,所以也等于2a + 2b
。
我们联立这两个式子,可以表示出a
:
Copyright 2015-2022 欧洲地质网版权所有 备案号:沪ICP备2022005074号-23 联系邮箱: 58 55 97 3@qq.com