鍊錶中環的入口結點問題是一個超級經典的問題,不管是在面試中,還是考研的過程中都是一個經典問題。通常公認的解法就是雙指針(快慢指針)的解法,當然這已經的老生長談的了。今天我們就來介紹介紹。
給定一個鍊錶,如果它是有環鍊錶,實作一個演算法回傳環路的開頭節點。有環鍊錶的定義:在鍊錶中某個節點的next元素指向在它前面出現過的節點,則表示該鍊錶存在環路。
解題思路1
遍歷鍊錶,同時將每次的結果放到map 中,如果有元素重複出現,則是有環形鍊錶
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func detectCycle(head *ListNode) *ListNode { visited := make(map[*ListNode]struct{}, 1) work := head for work != nil { _, ok := visited[work] if ok { return work } else { visited[work] = struct{}{} } work = work.Next } return nil}
解題思路2
快慢指針求解:我們定義兩個指針,一快一滿。慢指針每次只移動一步,而快指針每次移動兩步。初始時,慢指針在位置 head,而快指針在位置 head.next。這樣一來,如果在移動的過程中,快指針反過來追上慢指針,就表示該鍊錶為環形鍊錶。否則快指針將到達鍊錶尾部,此鍊錶不為環形鍊錶。
/** * Definition for a singly-linked list. * class ListNode { * public $val = 0; * public $next = null; * function __construct($val) { $this->val = $val; } * } */class Solution { /** * @param ListNode $head * @return Boolean */ function hasCycle($head) { $fast = $head; $slow = $head; while ($fast != null && $fast->next != null) { $fast = $fast->next->next; $slow = $slow->next; if ($fast === $slow) { return true; } } return false; }}
推薦:《2021年PHP面試題大匯總(收藏)》《php影片教學》
以上是PHP和Go如何進行環路鍊錶檢測的詳細內容。更多資訊請關注PHP中文網其他相關文章!