南京推廣公司seo sem是啥
題目描述
給定一個鏈表,如果它是有環(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)容
。