PHP和Go如何進行環路鍊錶檢測

醉折花枝作酒筹
發布: 2023-03-11 20:42:01
轉載
1953 人瀏覽過

鍊錶中環的入口結點問題是一個超級經典的問題,不管是在面試中,還是考研的過程中都是一個經典問題。通常公認的解法就是雙指針(快慢指針)的解法,當然這已經的老生長談的了。今天我們就來介紹介紹。

給定一個鍊錶,如果它是有環鍊錶,實作一個演算法回傳環路的開頭節點。有環鍊錶的定義:在鍊錶中某個節點的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中文網其他相關文章!

相關標籤:
來源:hxd.life
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板