鏈表中環(huán)的入口結(jié)點(diǎn)問(wèn)題是一個(gè)超級(jí)經(jīng)典的問(wèn)題，不管是在面試中，還是考研的過(guò)程中都是一個(gè)經(jīng)典問(wèn)題。通常的公認(rèn)解法就是雙指針(快慢指針)的解法，當(dāng)然這已經(jīng)的老生長(zhǎng)談的了。今天我們就來(lái)介紹介紹。

給定一個(gè)鏈表，如果它是有環(huán)鏈表，實(shí)現(xiàn)一個(gè)算法返回環(huán)路的開頭節(jié)點(diǎn)。 有環(huán)鏈表的定義：在鏈表中某個(gè)節(jié)點(diǎn)的next元素指向在它前面出現(xiàn)過(guò)的節(jié)點(diǎn)，則表明該鏈表存在環(huán)路。

解題思路 1

遍歷鏈表，同時(shí)將每次的結(jié)果放到 map 中，如果有元素重復(fù)出現(xiàn)，則是有環(huán)形鏈表

/**  * 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

快慢指針求解：我們定義兩個(gè)指針，一快一滿。慢指針每次只移動(dòng)一步，而快指針每次移動(dòng)兩步。初始時(shí)，慢指針在位置 head，而快指針在位置 head.next。這樣一來(lái)，如果在移動(dòng)的過(guò)程中，快指針?lè)催^(guò)來(lái)追上慢指針，就說(shuō)明該鏈表為環(huán)形鏈表。否則快指針將到達(dá)鏈表尾部，該鏈表不為環(huán)形鏈表。

/**  * 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年P(guān)HP面試題大匯總（收藏）》《php視頻教程》