[PYTHON] Soit Code Jour 84 à partir de zéro "142. Cycle de liste liée II"

Aperçu

Il semble que des tests de codage soient menés à l'étranger lors d'entretiens d'ingénieurs, et dans de nombreux cas, l'essentiel est d'implémenter des fonctions et des classes spécifiques en fonction du thème.

Apparemment, de nombreux ingénieurs prennent des mesures sur le site appelé LetCode.

C'est un site qui forme la puissance de l'algorithme qui peut résister au test de codage effectué au début, et c'est un chemin inévitable pour ceux qui veulent faire carrière dans une entreprise de technologie à l'étranger.

Je l'ai écrit en grand, mais je n'ai pas l'intention d'avoir une telle interview pour le moment.

Cependant, en tant qu'ingénieur informatique, il serait préférable d'avoir le même niveau de puissance d'algorithme qu'une personne, alors j'aimerais résoudre le problème de manière irrégulière et écrire la méthode que je pensais à ce moment-là sous forme de mémo.

Leetcode

Je le résolve avec Python3.

Table de codes Leet commençant à zéro

Dernière fois Leet Code Day 83 "102. Traversée de l'ordre au niveau de l'arborescence binaire" à partir de zéro

Twitter Je le fais.

** Blog technique Commencé! !! ** ** Je pense que la technologie écrira sur LetCode, Django, Nuxt, etc. ** C'est plus rapide à mettre à jour **, merci pour votre coopération!

problème

142. Linked List Cycle Ⅱ Le niveau de difficulté est moyen. Comme c'était le cas la dernière fois, il s'agit d'un extrait de la collection de problèmes.

Le problème est similaire au format du [Cycle de liste liée] précédemment résolu (https://qiita.com/KueharX/items/20f411ebf1c53cff2208). Une liste concaténée est donnée. Renvoie le nœud où commence le cycle de cette liste concaténée. S'il n'y a pas de cycle, il renvoie null.

Pour représenter le cycle dans une liste concaténée donnée, utilisez l'entier pos à la fin de la liste concaténée pour représenter la position de connexion (index 0). Si pos est -1, il n'y a pas de cycles dans la liste chaînée.

Remarque: ne modifiez pas la liste liée.

Example 1:

Input: head = [3,2,0,-4], pos = 1 Output: tail connects to node index 1 Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0 Output: tail connects to node index 0 Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1 Output: no cycle Explanation: There is no cycle in the linked list.

Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if not head:
            return None
        root,dic = head,{}
        while root:
            if root in dic:
                return root
            dic[root] = 1
            root = root.next
        return root
# Runtime: 56 ms, faster than 51.83% of Python3 online submissions for Linked List Cycle II.
# Memory Usage: 16.9 MB, less than 51.15% of Python3 online submissions for Linked List Cycle II.

Je l'ai géré à l'aide d'un dictionnaire.

Quand je l'ai reconsidéré plus tard, j'ai senti qu'il serait plus facile à comprendre si je le résolvais en utilisant deux pointeurs, mais je pense que c'est bien cette fois. ~~ Il est le plus important de continuer à résoudre !! ~~

Alors c'est tout pour cette fois. Je vous remercie pour votre travail acharné.