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

醉折花枝作酒筹
Freigeben: 2023-03-11 20:42:01
nach vorne
1953 Leute haben es durchsucht

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}
Nach dem Login kopieren

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;
    }}
Nach dem Login kopieren

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!

Verwandte Etiketten:
Quelle:hxd.life
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage