亚马逊又考了这道题

文章正文
发布时间:2024-07-15 00:55

亚马逊又考了这道题

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 元的优惠券,如果你信得过吴师兄,欢迎你的加入,或许学好算法,能让你在程序员的道路上走的更远一些。返回搜狐,查看更多

责任编辑: