So erkennen Sie zyklisch verknüpfte Listen in PHP und Go

Das Problem des Eintrittsknotens des Rings in der verknüpften Liste ist eine sehr klassische Frage, sei es in einem Vorstellungsgespräch oder im Rahmen einer postgradualen Aufnahmeprüfung. Die allgemein akzeptierte Lösung ist die Lösung von Doppelzeigern (schnelle und langsame Zeiger). Darüber wird natürlich schon lange gesprochen. Heute stellen wir es vor.

Wenn es sich bei einer verknüpften Liste um eine zyklisch verknüpfte Liste handelt, implementieren Sie einen Algorithmus, um den Startknoten des Zyklus zurückzugeben. Die Definition einer ringverknüpften Liste: Wenn das nächste Element eines Knotens in der verknüpften Liste auf den Knoten zeigt, der davor erschien, zeigt dies an, dass es in der verknüpften Liste einen Zyklus gibt.

Problemlösungsidee 1

Durchlaufen Sie die verknüpfte Liste und fügen Sie jedes Ergebnis in die Karte ein. Wenn es wiederholte Elemente gibt, gibt es eine kreisförmige verknüpfte Liste

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

Problemlösungsidee 2

Schnelle und langsame Zeigerlösung: Wir Definiere zwei Die Hände sind schnell und voll. Der langsame Zeiger bewegt sich jeweils nur um einen Schritt, während sich der schnelle Zeiger jeweils um zwei Schritte bewegt. Zunächst befindet sich der langsame Zeiger an der Position head und der schnelle Zeiger an der Position head.next. Wenn der schnelle Zeiger während der Bewegung den langsamen Zeiger einholt, bedeutet dies, dass es sich bei der verknüpften Liste um eine zirkulär verknüpfte Liste handelt. Andernfalls erreicht der schnelle Zeiger das Ende der verknüpften Liste und die verknüpfte Liste ist keine zirkulär verknüpfte Liste.

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

Empfohlen: "Zusammenfassung der PHP-Interviewfragen 2021 (Sammlung)" "php-Video-Tutorial"

Das obige ist der detaillierte Inhalt vonSo erkennen Sie zyklisch verknüpfte Listen in PHP und Go. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!