演算法解析:查詢連結串列環結構的入口結點

語言: CN / TW / HK

查詢連結串列環結構的入口結點

上吳師兄的演算法課,刷leetcode時,遇到了 '查詢連結串列環結構的入口結點'這題.

看完 leetcode 的 '快慢指標,兩次賽跑'(我取的名) 的解法時,一臉懵逼.

結合 吳師兄給的 示例動圖/解析, 並 划水整整研究一上午後,

(注:此時作者處於,當前迭代末期,活相對較少,好學生請不要模仿)

總結出了這版 文字純享,無需公式,讓你的直覺接受這種設定! 版 演算法解析

大家可以先直接去做做原題

AlgoMooc:環形連結串列2

力扣:環形連結串列2 142題

題幹

給定一個連結串列,返回連結串列開始入環的第一個節點。 如果連結串列無環,則返回 null。

為了表示給定連結串列中的環,

我們使用整數 pos 來表示連結串列尾連線到連結串列中的位置(索引從 0 開始).

如果 pos 是 -1,則在該連結串列中沒有環。

注意,pos 僅僅是用於標識環的情況,並不會作為引數傳遞到函式中。

懵逼樹上懵逼果,懵逼樹下你和我

看到這題,第一反應是 在結點上做標記,路過一個結點,標記一下.

當然,此時leetcode給出了更優的set儲存解法,不影響原本資料.

此處也略提一下,理解簡單

js // 我想的是在節點上做標記,顯然用set更好,記住這思路 var detectCycle = function(head) { const visited = new Set(); while (head !== null) { if (visited.has(head)) { return head; } visited.add(head); head = head.next; } return null; };

重點

此時還給出了第二個更優解法 空間複雜度為O(1)

詮釋了什麼叫 我不理解,但我大受震撼.jpg

這裡直接講 解法 '快慢指標,兩次賽跑'

思路是,

第一次, 使用 快慢指標, 快指標每次移動2節點, 慢指標每次移動1節點.

當 快指標與慢指標 第一次相遇時, 當前節點 稱為 相遇點.

第二次, 使用 兩個慢指標, 慢指標1 從 相遇點出發, 慢指標2 從 節點頭出發,

當 兩個慢指標 第一次相遇時, 此時相遇節點 即為 環入口點.

無需公式,看完後,讓你的直覺接受這種設定!

話不多說,直接上解析,程式碼在後面

```js // 要理解 快慢指標 找鏈的環結構入口,要理解兩個重要結論, // 1.慢指標 走過的的長度 等於 環的長度 // 2.慢指標 從頭走到環入口的長度 等於 慢指標 從相遇點走完剩餘環的長度

// 假設 快指標 一次走 2個節點,慢指標 一次走 1個節點 // 假設 頭到環入口長度 a, 環長度 b. // 第 1 次相遇時, 快指標總路程 f,慢指標總路程 s,此時可得到兩個等式 // (注意是第1次相遇,如果繼續跑,第1次相遇後,s每跑1圈,f會跑2圈,會再次在這相遇,演算法只需要考慮第1次相遇就行) // f(快指標路程) = 2s(慢指標走的路程) (快指標是慢指標兩倍速) // f(快指標路程) = s(慢指標走的路程) + b(環的長度) // 得到 s = b (慢指標走的路程 就是 環的長度b) // 可理解為,第一次相遇的時候,s還剛進 第1圈,f已經多走了1圈環,所以 s=b // 所以得到 重要結論 (1) 慢指標路程 s = b 環的節點數

// 接下來要思考,直覺上來說,為什麼再次從頭開始走一個 慢指標2 // 同時從第一次相遇處 走 慢指標1,兩個慢指標必然會在 環入口處相遇? // 換句話說 為什麼 慢指標1 走完 剩餘環的長度(y),會等於 從頭到入環 的長度?

// 此時,我們整理下, 頭到環入口a, 環入口到相遇處(x), 環長度b // 很顯然 環的長度(b) = x(入口到相遇處) + y(相遇處到環入口) // 同時由結論(1) 環的長度(b) = s(慢指標路徑) = a(頭到環入口) + x(入口到相遇處) // x(入口到相遇處) + y(相遇處到環入口) = a(頭到環入口) + x(入口到相遇處)

// 語言解釋就是, 頭到相遇處, 相遇處再到環入口,是等長的,重合部分就是 入口到相遇處 // 路徑上來說,都減去重合部分(入口到相遇處x),剩餘部分路徑相等 // 如果 假設兩個慢指標,都不走重合部分,一個從頭開始走,一個跳過重合部分從相遇處開始走 // 相同速度,走過相同路徑時,便會相遇在入口

var detectCycle = function(head) { if (head === null) { return null; } let slow = head, fast = head; while (fast !== null) { slow = slow.next; if (fast.next !== null) { fast = fast.next.next; } else { return null; } if (fast === slow) { let ptr = head; while (ptr !== slow) { ptr = ptr.next; slow = slow.next; } return ptr; } } return null; }; ```

總結

如有疵漏,大佬輕噴,同時感謝指點.

如果這篇文章能幫到大家,就是我最大的快樂!!!