經(jīng)典面試題：環(huán)形鏈表的判斷與定位
? ? 作者：nettee ???????
公眾號：面向大象編程
大家好，我是 nettee。近期，我會跟大家分享一些「經(jīng)典面試題」，既講解題目的解法，也講解面試中的一些套路。
今天這篇文章要講解的題目是「環(huán)形鏈表」的兩道題目：
LeetCode 141. Linked List Cycle（Easy） LeetCode 142. Linked List Cycle II（Medium）
兩道題目都分別有「哈希表」的樸素解法，以及「雙指針」的巧妙解法。非常適合大家掌握面試中的答題思路。想順利通過面試的同學，不要錯過這篇文章喲。
判斷鏈表是否有環(huán)
鏈表是線性結(jié)構(gòu)，怎么會出現(xiàn)環(huán)呢？實際上是這道題中的鏈表經(jīng)過了特殊改造，鏈表尾部會額外增加一個指針，連接到鏈表中間的某個結(jié)點，如下圖所示。
我們今天要講的這兩道題，都是在這個結(jié)構(gòu)的基礎(chǔ)上出的題。
先看 141 題：
LeetCode 141. Linked List Cycle（Easy）
給定一個鏈表，判斷鏈表中是否有環(huán)。
示例：
輸入：
輸出：true
解釋：鏈表中有一個環(huán)，其尾部連接到第二個結(jié)點。
這道題其實是一道非常新穎的題目，考察的是對鏈表知識的綜合掌握。只靠背鏈表的遍歷代碼來解題的人，看到這道題會手足無措。因為鏈表加上環(huán)之后，普通的遍歷代碼根本就不管用了！
void?traverse(ListNode?head)?{
????for?(ListNode?q?=?head;?q?!=?null;?q?=?q.next)?{
????????//?...
????}
}
上面的這段遍歷代碼，在有環(huán)路的鏈表上，會陷入「無限循環(huán)」：指針 q 在環(huán)路中一直繞圈，永遠到達不了結(jié)束條件 q == null 。
解題基本思路
其實看到前面的鏈表遍歷代碼，很多同學應該已經(jīng)想出這道題的解題關(guān)鍵點了：
我只要順著鏈表遍歷，如果循環(huán)能正常退出（遇到 q == null 的情況），那么鏈表無環(huán)；如果循環(huán)永遠不能退出，那么鏈表有環(huán)。
那么難點又來了，如果循環(huán)永遠不能退出，我們的代碼根本結(jié)束不了，不能返回「鏈表有環(huán)」的結(jié)果……
面試小貼士：
在面試中，我們經(jīng)常會遇到以上的情況。自己有了一點思路，但是還不能確定思路對不對。這時候，我們要做的不是「悶頭苦想」直到想出最終解法，而是應該及時把自己關(guān)鍵的思路說給面試官。
面試中最忌諱的是長時間的沉默。及時跟面試官反饋我們初步的思路，可以確定我們的思路是否正確。即使一開始一點思路都沒有，也可以直接說出來，請面試官給一點提示。
此時，面試官會告訴我們，以上的思路是正確的。接下來，我們需要能夠判斷鏈表有環(huán)的情況，并及時退出循環(huán)。
那么究竟如何判斷呢？可以使用樸素的「哈希表」方案，或者是巧妙的「雙指針」方法，下面會分別介紹。
哈希表解法
哈希表解法的基本思路是：把訪問過的結(jié)點記錄下來，如果在遍歷中遇到了訪問過的結(jié)點，那么可以確定鏈表中存在環(huán)。記錄訪問過的結(jié)點，最常用的方法就是使用哈希表了。
有了這一點思路之后，我們很快可以寫出相應的題解代碼：
public?boolean?hasCycle(ListNode?head)?{
????//?記錄已訪問過的結(jié)點
????Set?seen?=?new?HashSet<>();
????for?(ListNode?q?=?head;?q?!=?null;?q?=?q.next)?{
????????if?(seen.contains(q))?{
????????????//?遇到已訪問過的結(jié)點，確定鏈表存在環(huán)
????????????return?true;
????????}
????????seen.add(q);
????}
????//?遍歷循環(huán)正常退出，鏈表不存在環(huán)
????return?false;
}
這樣，我們就成功地解決了這道題目。
但接下來面試官會讓我們分析算法的時間、空間復雜度。發(fā)現(xiàn)空間復雜度是 之后，面試官會讓我們再寫一個空間復雜度更低的解法，也就是說，我們不能使用哈希表這樣的額外存儲空間了。
雙指針解法
在面試中，做出上面的哈希表解法屬于「基本達標」，可以打 70 分了，但是如果要讓面試官青睞你，打到 90 分，還要能寫出不使用額外存儲空間的解法，也就是雙指針解法。
實話說，要在面試中憑空想出雙指針解法有點困難。因此，這要靠我們平時的積累，多見識不同的解題技巧，這樣在面試中可以熟練運用。
鏈表中的雙指針技巧也叫「快慢指針」，指的是用兩個指針一快一慢同時遍歷鏈表。
例如，尋找鏈表中點的操作。使用一快一慢兩個指針。快指針一次前進兩個結(jié)點，速度是慢指針的兩倍。當快指針到達鏈表尾部時，慢指針正好到達的鏈表的中部，這樣就找到的鏈表的中點，非常巧妙。遍歷過程如下圖所示。
如果我們熟悉這個技巧，就可以在環(huán)形鏈表這道題中觸類旁通，使用出快慢指針技巧。
我們讓快指針一次前進兩個結(jié)點，慢指針一次前進一個結(jié)點。當快慢指針都進入環(huán)路時，快指針會將慢指針「套圈」，從后面追上慢指針，如下圖所示。
這樣，如果快指針追上了慢指針，我們就可以判斷鏈表中存在環(huán)路。而如果鏈表中不存在環(huán)的話，快指針會永遠走在慢指針的前面，它們不會相遇。
依照這個思路，我們可以寫出以下的題解代碼。
public?boolean?hasCycle(ListNode?head)?{
????ListNode?fast?=?head;
????ListNode?slow?=?head;
????while?(fast?!=?null?&&?fast.next?!=?null)?{
????????fast?=?fast.next.next;
????????slow?=?slow.next;
????????//?fast?和?slow?指向同一個結(jié)點，說明存在“套圈”
????????if?(fast?==?slow)?{
????????????return?true;
????????}
????}
????//?fast?到達鏈表尾部，則不存在環(huán)
????return?false;
}
代碼簡潔，解釋清晰，那么這道面試算法題，你可以得 100 分。
尋找鏈表環(huán)的起點
LeetCode 142 這道題，其實相當于 141 的「第二問」。當你用雙指針解決了「判斷環(huán)形鏈表」的題目之后，面試官看你答得不錯，可能會繼續(xù)追問，如何尋找環(huán)形鏈表的環(huán)的起點？如果你能答出這一問，可以得 120 分。
LeetCode 142. Linked List Cycle II（Medium）
給定一個鏈表，返回鏈表開始入環(huán)的第一個節(jié)點。如果鏈表無環(huán)，則返回
null。不允許修改給定的鏈表。示例：
輸入：
輸出：結(jié)點 <2>
解釋：鏈表中有一個環(huán)，其尾部連接到第二個結(jié)點。
如果用哈希表的方法，這道題其實和前一題是一樣的，沒什么難度。因此，面試官要求你用雙指針的方法尋找鏈表環(huán)的起點。
乍一看來，這道題挺難的。我們可以用快慢指針的方法知道鏈表中是否存在環(huán)，但我們不知道兩個指針相遇在什么位置，要找到環(huán)的起點就更難了。不過不要慌，我們先畫個圖看看兩個指針相遇的過程：
如上圖所示，鏈表分為兩段：無環(huán)段和有環(huán)段。我們設(shè)無環(huán)段的長度為 ，環(huán)的長度為 。當快慢指針相遇時，我們設(shè)慢指針已經(jīng)走了 步，那么快指針這時候已經(jīng)走了 步。快指針套圈了慢指針，也就是比慢指針多走了若干圈。我們可以列出公式：
其中， 可以是任意正整數(shù)，因為快指針可能套了慢指針不止一圈。將上式化簡得到
這個 恰好是慢指針走的步數(shù)。也就是說，慢指針目前前進的 步，正好是環(huán)的長度 的整數(shù)倍。
那么，慢指針再走 步，就可以正好到達環(huán)的起點（圖中的 S 點）。這是因為，，正好夠從鏈表頭部出發(fā)，走一段無環(huán)段（），再把有環(huán)段走 圈（）。
如果我們在此時再用一個指針 q 從鏈表頭部出發(fā)。那么指針 q 和慢指針 slow 會在走了 步以后恰好在環(huán)的起點處相遇。這樣，我們就可以知道環(huán)的起點了。
根據(jù)以上思路，我們可以寫出下面的題解代碼：
public?ListNode?detectCycle(ListNode?head)?{
????ListNode?fast?=?head;
????ListNode?slow?=?head;
????while?(fast?!=?null?&&?fast.next?!=?null)?{
????????fast?=?fast.next.next;
????????slow?=?slow.next;
????????//?快慢指針相遇，說明鏈表存在環(huán)
????????if?(fast?==?slow)?{
????????????//?此時?slow?指針距離環(huán)的起點的距離恰好為?a
????????????ListNode?q?=?head;
????????????while?(q?!=?slow)?{
????????????????slow?=?slow.next;
????????????????q?=?q.next;
????????????}
????????????//?slow?和?q?相遇的位置一定是環(huán)的起點
????????????return?slow;
????????}
????}
????//?鏈表不存在環(huán)，返回?null
????return?null;
}
如果你能思考出以上內(nèi)容并寫出結(jié)果，那么面試官會非常認可你，這場面試基本就比較穩(wěn)了。
面試套路總結(jié)
從以上的講解過程中我們可以發(fā)現(xiàn)，這個環(huán)形鏈表的題目其實可以分成幾個小問，難度層層遞進：
用哈希表的方法判斷鏈表是否存在環(huán) 用快慢指針的方法判斷鏈表是否存在環(huán) 用快慢指針的方法尋找環(huán)的起點
在面試中，面試官往往會先拋出比較簡單的一兩個小問進行「試探」。當發(fā)現(xiàn)你回答得還不錯，則會繼續(xù)提更難的問題，知道你不會為止。如果你一開始就回答得不好，那么面試官可能會認為你在這一塊的掌握很一般，很快轉(zhuǎn)而問其他的問題。
把握清楚面試中的這個「層層遞進」的規(guī)律，我們要注意兩點：
第一，在平時復習的時候要注意基礎(chǔ)。也許你能做出很多高難度的題目，但如果在簡單的題目上回答不上來，面試官可能就不會繼續(xù)問了，你解決難題的能力可能也發(fā)揮不上來。
第二，面試中如果遇到很難的題目、一點也答不上來，不要氣餒。這時候很可能是面試官在試探你能力的邊界在哪里，側(cè)面說明了你前面可能表現(xiàn)得不錯。所以說在面試的全程中都要不慌不忙，會就正常回答，不會就直接說不知道。例如本文例題「尋找環(huán)的起點」，其實能在面試中做出來的人不多，能把「判斷環(huán)是否存在」做好就已經(jīng)很不錯了。
本文的講解就到此結(jié)束，希望能對你后面的面試有所幫助~
往期文章
我是 nettee，致力于分享面試算法的解題套路，讓你真正掌握解題技巧，做到舉一反三。我的《LeetCode 例題精講》系列文章正在寫作中，關(guān)注我的公眾號，獲取最新文章。
原創(chuàng)不易，歡迎分享、點贊和「在看」 ?