LeetCode 141. Exemple de solution de cycle de liste liée (Python)

LeetCode question 141. Voici un exemple de réponse à Linked List Cycle en Python. https://leetcode.com/problems/linked-list-cycle/

Aperçu du problème

L'énoncé du problème est simple: étant donné une liste chaînée, déterminez si elle contient un cycle., Étant donné une liste chaînée. L'argument est une liste chaînée.

Comment résoudre

L'algorithme de résolution est simple. Prenons l'exemple 1 de l'énoncé du problème comme exemple. Tout d'abord, le graphique en question (appelé ici un graphique car il ressemble à un graphique en tant que structure de données, et non à un graphique jusqu'aux mathématiques du secondaire).

Considérons maintenant le pointeur lent et le pointeur rapide. Le point de départ ici est le 3 le plus à gauche. Le pointeur lent avance un à la fois et le pointeur rapide avance deux à la fois. Maintenant, si vous continuez une fois ici, cela ressemblera à la figure ci-dessous.

Après avoir procédé deux fois, ce sera comme indiqué dans la figure ci-dessous.

Après avoir procédé 3 fois, ce sera comme indiqué dans la figure ci-dessous.

Après être allés trois fois, le pointeur lent et le pointeur rapide sont arrivés au même endroit (nœud 4).

Exemple de réponse

Voici deux exemples de réponses.

Exemple de réponse 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

Le résultat de l'exécution de l'exemple de réponse 1 est le suivant. Au moment de cette exécution, il semble être 64,54% plus rapide que la soumission moyenne en Python3. De même, l'utilisation de la mémoire semble être 100% inférieure à cela.

Exemple de réponse 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

Le résultat de l'exécution de l'exemple de réponse 2 est le suivant. Au moment de cette exécution, il semble être 33,8% plus rapide que la soumission moyenne en Python3. De même, l'utilisation de la mémoire semble être 100% inférieure à cela. On pense que la raison pour laquelle la vitesse de traitement est plus lente que dans l'exemple de réponse 1 est que try except effectue le traitement de jugement à chaque fois et que l'instruction if est augmentée de un, donc elle est plus lente de ce montant.