PHP和Go怎么進行環路鏈表檢測

這篇文章主要介紹“PHP和Go怎么進行環路鏈表檢測”，在日常操作中，相信很多人在PHP和Go怎么進行環路鏈表檢測問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”PHP和Go怎么進行環路鏈表檢測”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

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

給定一個鏈表，如果它是有環鏈表，實現一個算法返回環路的開頭節點。 有環鏈表的定義：在鏈表中某個節點的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;
    }}

到此，關于“PHP和Go怎么進行環路鏈表檢測”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！