PHP と Go でサイクルリンクリストを検出する方法

リンクリストのリングのエントリノードの問題は、面接でも大学院入試でも超定番の質問です。一般に受け入れられている解決策は、ダブル ポインタ (高速ポインタと低速ポインタ) による解決策です。もちろん、これについては長い間議論されてきました。今日はそれを紹介します。

リンク リストが循環リンク リストである場合、サイクルの開始ノードを返すアルゴリズムを実装します。リングリンクリストの定義: リンクリスト内のノードの次の要素が、その前に現れたノードを指している場合、それはリンクリスト内にサイクルがあることを示します。

解決策のアイデア 1

リンク リストをトラバースし、各結果をマップに入力します。要素が繰り返される場合は、循環リンク リストが存在します。

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

高速ポインタと低速ポインタのソリューション: 高速ポインタとフル ポインタの 2 つのポインタを定義します。低速ポインタは一度に 1 ステップのみ移動しますが、高速ポインタは一度に 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 中国語 Web サイトの他の関連記事を参照してください。