亚马逊又考了这道题
2022-04-25 14:05
大家好，我是吴师兄。
今天这篇文章要讲解的题目是「环形链表」的两道题目：
LeetCode 141. Linked List Cycle（Easy）
LeetCode 142. Linked List Cycle II（Medium）
两道题目都分别有「哈希表」的朴素解法，以及「双指针」的巧妙解法。非常适合大家掌握面试中的答题思路。
想顺利通过面试的同学，不要错过这篇文章哟。
这类题目外企非常喜欢考察，给大家看一下近半年考察的频率。
判断链表是否有环
链表是线性结构，怎么会出现环呢？实际上是这道题中的链表经过了特殊改造，链表尾部会额外增加一个指针，连接到链表中间的某个结点，如下图所示。
链表尾部额外增加一个指针，形成环路
我们今天要讲的这两道题，都是在这个结构的基础上出的题。
先看 141 题：
LeetCode 141. Linked List Cycle（Easy）
给定一个链表，判断链表中是否有环。
示例：
输入：
输出：true
解释：链表中有一个环，其尾部连接到第二个结点。
这道题其实是一道非常新颖的题目， 考察的是对链表知识的综合掌握。只靠背链表的遍历代码来解题的人，看到这道题会手足无措。因为链表加上环之后，普通的遍历代码根本就不管用了！
voidtraverse(ListNode head){
for(ListNode q = head; q != null; q = q.next) {
// ...
}
}
上面的这段遍历代码，在有环路的链表上，会陷入「无限循环」：指针 q 在环路中一直绕圈，永远到达不了结束条件 q == null 。
解题基本思路
其实看到前面的链表遍历代码，很多同学应该已经想出这道题的解题关键点了：
我只要顺着链表遍历，如果循环能正常退出（遇到 q == null 的情况），那么链表无环；如果循环永远不能退出，那么链表有环。
那么难点又来了，如果循环永远不能退出，我们的代码根本结束不了，不能返回「链表有环」的结果……
面试小贴士：
在面试中，我们经常会遇到以上的情况。自己有了一点思路，但是还不能确定思路对不对。这时候，我们要做的不是「闷头苦想」直到想出最终解法，而是应该及时把自己关键的思路说给面试官。
面试中最忌讳的是长时间的沉默。及时跟面试官反馈我们初步的思路，可以确定我们的思路是否正确。即使一开始一点思路都没有，也可以直接说出来，请面试官给一点提示。
此时，面试官会告诉我们，以上的思路是正确的。接下来，我们需要能够判断链表有环的情况，并及时退出循环。
那么究竟如何判断呢？可以使用朴素的「哈希表」方案，或者是巧妙的「双指针」方法，下面会分别介绍。
哈希表解法
哈希表解法的基本思路是： 把访问过的结点记录下来，如果在遍历中遇到了访问过的结点，那么可以确定链表中存在环。记录访问过的结点，最常用的方法就是使用哈希表了。
有了这一点思路之后，我们很快可以写出相应的题解代码：
publicbooleanhasCycle(ListNode head){
// 记录已访问过的结点
Set<ListNode> seen = newHashSet<>;
for(ListNode q = head; q != null; q = q.next) {
if(seen.contains(q)) {
// 遇到已访问过的结点，确定链表存在环
returntrue;
}
seen.add(q);
}
// 遍历循环正常退出，链表不存在环
returnfalse;
}
这样，我们就成功地解决了这道题目。
但接下来面试官会让我们分析算法的时间、空间复杂度。发现空间复杂度是 之后，面试官会让我们再写一个空间复杂度更低的解法，也就是说，我们不能使用哈希表这样的额外存储空间了。
双指针解法
在面试中，做出上面的哈希表解法属于「基本达标」，可以打 70 分了，但是如果要让面试官青睐你，打到 90 分，还要能写出不使用额外存储空间的解法，也就是双指针解法。
实话说，要在面试中凭空想出双指针解法有点困难。因此，这要靠我们平时的积累，多见识不同的解题技巧，这样在面试中可以熟练运用。
链表中的双指针技巧也叫「快慢指针」，指的是用两个指针一快一慢同时遍历链表。
例如， 寻找链表中点的操作。使用一快一慢两个指针。快指针一次前进两个结点，速度是慢指针的两倍。当快指针到达链表尾部时，慢指针正好到达的链表的中部，这样就找到的链表的中点，非常巧妙。遍历过程如下图所示。
使用快慢指针寻找链表中点（动图）
如果我们熟悉这个技巧，就可以在环形链表这道题中触类旁通，使用出快慢指针技巧。
我们让快指针一次前进两个结点，慢指针一次前进一个结点。当快慢指针都进入环路时，快指针会将慢指针「套圈」，从后面追上慢指针，如下图所示。
在环路中，快指针套圈慢指针（动图）
这样，如果快指针追上了慢指针，我们就可以判断链表中存在环路。而如果链表中不存在环的话，快指针会永远走在慢指针的前面，它们不会相遇。
依照这个思路，我们可以写出以下的题解代码。
publicbooleanhasCycle(ListNode head){
ListNode fast = head;
ListNode slow = head;
while(fast != null&& fast.next != null) {
fast = fast.next.next;
slow = slow.next;
// fast 和 slow 指向同一个结点，说明存在“套圈”
if(fast == slow) {
returntrue;
}
}
// fast 到达链表尾部，则不存在环
returnfalse;
}
代码简洁，解释清晰，那么这道面试算法题，你可以得 100 分。
寻找链表环的起点
LeetCode 142 这道题，其实相当于 141 的「第二问」。当你用双指针解决了「判断环形链表」的题目之后，面试官看你答得不错，可能会继续追问，如何寻找环形链表的环的起点？如果你能答出这一问，可以得 120 分。
LeetCode 142. Linked List Cycle II（Medium）
给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null 。不允许修改给定的链表。
示例：
输入：
输出：结点 <2>
解释：链表中有一个环，其尾部连接到第二个结点。
如果用哈希表的方法，这道题其实和前一题是一样的，没什么难度。因此，面试官要求你用双指针的方法寻找链表环的起点。
乍一看来，这道题挺难的。我们可以用快慢指针的方法知道链表中是否存在环，但我们不知道两个指针相遇在什么位置，要找到环的起点就更难了。不过不要慌，我们先画个图看看两个指针相遇的过程：
两个指针相遇的过程
如上图所示，链表分为两段：无环段和有环段。我们设无环段的长度为 ，环的长度为 。当快慢指针相遇时，我们设慢指针已经走了 步，那么快指针这时候已经走了 步。快指针套圈了慢指针，也就是比慢指针多走了若干圈。我们可以列出公式：
其中， 可以是任意正整数，因为快指针可能套了慢指针不止一圈。将上式化简得到
这个 恰好是慢指针走的步数。也就是说，慢指针目前前进的 步，正好是环的长度 的整数倍。
那么， 慢指针再走 步，就可以正好到达环的起点 （图中的 S 点）。这是因为， ，正好够从链表头部出发，走一段无环段（ ），再把有环段走 圈（ ）。
如果我们在此时再用一个指针 q 从链表头部出发。那么指针 q 和慢指针 slow 会在走了 步以后恰好在环的起点处相遇。这样，我们就可以知道环的起点了。
根据以上思路，我们可以写出下面的题解代码：
publicListNode detectCycle(ListNode head){
ListNode fast = head;
ListNode slow = head;
while(fast != null&& fast.next != null) {
fast = fast.next.next;
slow = slow.next;
// 快慢指针相遇，说明链表存在环
if(fast == slow) {
// 此时 slow 指针距离环的起点的距离恰好为 a
ListNode q = head;
while(q != slow) {
slow = slow.next;
q = q.next;
}
// slow 和 q 相遇的位置一定是环的起点
returnslow;
}
}
// 链表不存在环，返回 null
returnnull;
}
如果你能思考出以上内容并写出结果，那么面试官会非常认可你，这场面试基本就比较稳了。
面试套路总结
从以上的讲解过程中我们可以发现，这个环形链表的题目其实可以分成几个小问，难度层层递进：
用哈希表的方法判断链表是否存在环
用快慢指针的方法判断链表是否存在环
用快慢指针的方法寻找环的起点
在面试中，面试官往往会先抛出比较简单的一两个小问进行「试探」。当发现你回答得还不错，则会继续提更难的问题，知道你不会为止。如果你一开始就回答得不好，那么面试官可能会认为你在这一块的掌握很一般，很快转而问其他的问题。
把握清楚面试中的这个「层层递进」的规律，我们要注意两点：
第一，在平时复习的时候要注意基础。也许你能做出很多高难度的题目，但如果在简单的题目上回答不上来，面试官可能就不会继续问了，你解决难题的能力可能也发挥不上来。
第二，面试中如果遇到很难的题目、一点也答不上来，不要气馁。这时候很可能是面试官在试探你能力的边界在哪里，侧面说明了你前面可能表现得不错。所以说在面试的全程中都要不慌不忙，会就正常回答，不会就直接说不知道。例如本文例题「寻找环的起点」，其实能在面试中做出来的人不多，能把「判断环是否存在」做好就已经很不错了。
本文的讲解就到此结束，希望能对你后面的面试有所帮助~
最后
最后，欢迎想要刷题进大厂的小伙伴加入吴师兄的算法训练营，目前已经开展五期了。
很多零基础的同学第一天的学习，一口气刷了 5 题！
有的同学看动画居然嗨起来，每天学六个小时还乐此不疲，从早到晚追问我问题。
一对一答疑，解决你的所有疑惑。
每周的直播细致的讲解和答疑。
训练营已经顺利开展五期，这里有一些 200 元的优惠券，如果你信得过吴师兄，欢迎你的加入，或许学好算法，能让你在程序员的道路上走的更远一些。返回搜狐，查看更多
责任编辑：
