PHP和Go如何進(jìn)行環(huán)路鏈表檢測(cè)

本篇內(nèi)容介紹了“PHP和Go如何進(jìn)行環(huán)路鏈表檢測(cè)”的有關(guān)知識(shí)，在實(shí)際案例的操作過(guò)程中，不少人都會(huì)遇到這樣的困境，接下來(lái)就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

給定一個(gè)鏈表，如果它是有環(huán)鏈表，實(shí)現(xiàn)一個(gè)算法返回環(huán)路的開(kāi)頭節(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è)指針，一快一滿(mǎn)。慢指針每次只移動(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;
}}

“PHP和Go如何進(jìn)行環(huán)路鏈表檢測(cè)”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！