LeetCode 141. Lösungsbeispiel für verknüpfte Listenzyklen (Python)

LeetCode-Frage 141. Hier ist ein Beispiel für die Antwort auf den Zyklus der verknüpften Liste in Python. https://leetcode.com/problems/linked-list-cycle/

Problemübersicht

Die Problemstellung ist einfach: Bestimmen Sie anhand einer verknüpften Liste, ob sie einen Zyklus enthält. Geben Sie eine verknüpfte Liste an. Das Argument ist eine verknüpfte Liste.

Wie löst man

Der Algorithmus zum Lösen ist einfach. Betrachten wir als Beispiel Beispiel 1 der Problemstellung. Erstens das fragliche Diagramm (hier als Diagramm bezeichnet, da es einem Diagramm als Datenstruktur ähnelt, nicht einem Diagramm bis zur Mathematik der High School).

Betrachten Sie nun den langsamen und den schnellen Zeiger. Der Ausgangspunkt ist hier ganz links 3. Der langsame Zeiger rückt nacheinander vor, und der schnelle Zeiger rückt jeweils um zwei vor. Wenn Sie hier einmal fortfahren, sieht es wie in der folgenden Abbildung aus.

Nach zweimaligem Fortfahren wird es wie in der folgenden Abbildung gezeigt.

Nach dreimaligem Fortfahren wird dies wie in der folgenden Abbildung gezeigt.

Nach dreimaligem Gehen kamen der langsame Zeiger und der schnelle Zeiger an dieselbe Stelle (Knoten 4).

Antwortbeispiel

Nachfolgend finden Sie zwei Beispiele für Antworten.

Antwortbeispiel 1

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        """
        type head: ListNode
        return type: bool
        """

        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

Das Ausführungsergebnis von Antwortbeispiel 1 ist wie folgt. Zum Zeitpunkt dieses Laufs scheint es 64,54% schneller zu sein als die durchschnittliche Übermittlung in Python3. Ebenso scheint die Speichernutzung 100% geringer zu sein.

Antwortbeispiel 2

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        """
        type head: ListNode
        return type: bool
        """

        try:
            slow = head
            fast = head.next
            while slow != fast:
                slow = slow.next
                fast = fast.next.next
                
            return True
        except:
            return False

Das Ausführungsergebnis von Antwortbeispiel 2 ist wie folgt. Zum Zeitpunkt dieses Laufs scheint es 33,8% schneller zu sein als die durchschnittliche Übermittlung in Python3. Ebenso scheint die Speichernutzung 100% geringer zu sein. Es wird angenommen, dass der Grund, warum die Verarbeitungsgeschwindigkeit langsamer als das Antwortbeispiel 1 ist, darin besteht, dass try außer die Beurteilungsverarbeitung jedes Mal durchführt und die if-Anweisung um eins erhöht wird, sodass sie um diesen Betrag langsamer ist.