題目描述

給定一個鏈表，如果它是有環(huán)鏈表，實現(xiàn)一個算法返回環(huán)路的開頭節(jié)點。若環(huán)不存在，請返回 null。
題目傳送門：面試題 02.08. 環(huán)路檢測

• 如果鏈表中有某個節(jié)點，可以通過連續(xù)跟蹤 next 指針再次到達，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該鏈表中沒有環(huán)。注意：pos 不作為參數(shù)進行傳遞，僅僅是為了標識鏈表的實際情況。

示例 1：

 輸入：head = [3,2,0,-4], pos = 1輸出：tail connects to node index 1解釋：鏈表中有一個環(huán)，其尾部連接到第二個節(jié)點。

示例 2：

輸入：head = [1,2], pos = 0
輸出：tail connects to node index 0
解釋：鏈表中有一個環(huán)，其尾部連接到第一個節(jié)點。

示例 3：

輸入：head = [1], pos = -1
輸出：no cycle
解釋：鏈表中沒有環(huán)。

進階：

• 你是否可以不用額外空間解決此題？

解題思路與代碼

• 這道題算是比較簡單的一道題。檢測鏈表是否存在環(huán)的最簡單的一種方法是哈希法，其次就是快慢指針法。那么前者的空間復雜度可能會高些，但是代碼結(jié)構(gòu)簡單易懂。

• 后者雖然說比前者稍微難點，但也沒有難太多，多了一點點的思考量而已。

總的來說，這道題是一道好題，考驗了你一點點的數(shù)學思維，與鏈表的實際操作

方案一：哈希法

這道題如果是單單的判斷鏈表是否成環(huán)，那這道題就是一道簡單題，如果還要讓你去返回成環(huán)的開頭節(jié)點，那這道題的難度就要上升了。

對于這道題，如果我們用了哈希法，那就是降維打擊，因為我們利用unordered_set就可以直接幫你返回相同節(jié)點。
具體的代碼如下：

class Solution {
public:ListNode *detectCycle(ListNode *head) {unordered_set<ListNode*> set;while(head){if(set.count(head)) return head;set.insert(head);head = head->next;}return nullptr;}
};

復雜度分析：

• 時間復雜度：O(n),其中n是鏈表節(jié)點的個數(shù)
• 空間復雜度：O(n),我們需要將鏈表的每一個節(jié)點放入集合中，所以是O(n)

方案二： 快慢指針法

• 先解釋一下這里的快慢指針法是什么意思。在這里，我們先設(shè)置兩個指針，p1，p2。 p1一次走一格，p2一次走兩個。因為他們走的步數(shù)不一樣，所以，如果鏈表中有環(huán)存在了話，那么p1，p2一定不會相等。反之，如果有環(huán)，那p1，p2一定會相等。

那這道題的難點在成環(huán)節(jié)點，在距離頭節(jié)點多少位置呢？首先，我們要畫圖分析。

• 我們設(shè)從頭節(jié)點，到成環(huán)節(jié)點的距離為a，成環(huán)節(jié)點到p2追到p1的距離為b，被追到的p1節(jié)點距離再次回到成環(huán)節(jié)點的距離為c。

• p2指針一次走兩格，p1指針一次走一格，p2追上p1的時候，p2走過的距離是p1的兩倍。

• p1被追到時p2走了a + n(b + c) + b，p1走了a + b所以不難得出這個等式：a + n(b + c) + b = 2(a + b)

• 將這個等式變化一下便是 **a = c + (n-1)(b+c)**么。

看著這個圖，我們來翻譯一個這個數(shù)學等式的意思。

• 假設(shè)從頭節(jié)點走了a步，到達了成環(huán)節(jié)點。便等于我在相遇節(jié)點走了 c 步 + n圈。
• 我們在p1節(jié)點與p2節(jié)點相遇的時候，再去設(shè)置一個p3節(jié)點讓它等于頭節(jié)點。這個時候，p3也一次走一步。
• 你看圖，當p3在頭節(jié)點走了a步的時候，是不是正好與p1在b的時候走了c步 + n圈呢？

具體代碼如下：

class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* p1 = head;ListNode* p2 = head;while(p2){p1 = p1->next;if(p2->next)p2 = p2->next->next;else return nullptr;if(p1 == p2) {ListNode* p3 = head;while(p3!=p1){p1 = p1->next;p3 = p3->next;}return p3;}}return nullptr;}
};

復雜度分析：

• 時間復雜度：O(N),N為節(jié)點的長度。因為你在實際推演的過程中會發(fā)現(xiàn)，p1指針走過的最長的路程也不會超過鏈表中節(jié)點的個數(shù)，而是等于節(jié)點的個數(shù)，所以時間復雜度是O(N)
• 空間復雜度：O(1),我們設(shè)置了幾個變量而已，沒有使用額外的數(shù)據(jù)結(jié)構(gòu)，所以是O(1)。

總結(jié)

這道題目是一個經(jīng)典的鏈表問題，經(jīng)常出現(xiàn)在計算機科學和軟件工程的面試和教程中。

這道題目的主要意義和重要性可以從以下幾個方面來看：

• 數(shù)據(jù)結(jié)構(gòu)理解與應(yīng)用：這道題目需要你理解和操作鏈表這種基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)。理解數(shù)據(jù)結(jié)構(gòu)的特性和操作方法是編程和算法學習的基礎(chǔ)。

• 雙指針技巧：這道題目需要使用到雙指針（快慢指針）的技巧。這是一個常用的算法設(shè)計策略，可以幫助解決一些看似復雜的問題。

• 算法分析：通過這道題目，你需要理解和分析算法的時間復雜度和空間復雜度。這道題的解決方案有一個很好的性質(zhì)：它只需要常量的額外空間，且時間復雜度為線性。

• 問題解決和調(diào)試能力：這道題目也可以幫助你提升問題解決和調(diào)試的能力。理解為什么這個解決方案能夠工作，對于提升你的算法設(shè)計和問題解決能力是非常有幫助的。

所以，這道題目的意義不僅僅是解決一個具體的問題，更重要的是通過這個問題來學習和提升你的數(shù)據(jù)結(jié)構(gòu)知識，算法設(shè)計和問題解決能力。

最后的最后，如果你覺得我的這篇文章寫的不錯的話，請給我一個贊與收藏，關(guān)注我，我會繼續(xù)給大家?guī)砀喔鼉?yōu)質(zhì)的干貨內(nèi)容。