[leetcode] [python] 142. Cycle de liste liée II

142




Knowledge points: two pointers

1. Titre original

Étant donné une liste chaînée, renvoie le nœud où le cycle commence. S'il n'y a pas de cycle, renvoie null.



Pour représenter un cycle dans la liste chaînée donnée, nous utilisons un entier pos qui représente la position (indexée 0) dans la liste chaînée à laquelle se connecte tail. Si pos est -1, alors il n'y a pas de cycle dans la liste chaînée.



Remarque: ne modifiez pas la liste liée.



Exemple 1:

Entrée: head = [3,2,0, -4], pos = 1
Sortie: la queue se connecte à l'index de nœud 1
Explication: Il existe un cycle dans la liste chaînée, où tail se connecte au deuxième nœud.

Exemple 2:



Entrée: head = [1,2], pos = 0
Sortie: la queue se connecte à l'index de nœud 0
Explication: Il existe un cycle dans la liste chaînée, où tail se connecte au premier nœud.

Exemple 3:

Entrée: head = [1], pos = -1
Sortie: pas de cycle
Explication: Il n'y a pas de cycle dans la liste chaînée.

Suivre:
Pouvez-vous le résoudre sans utiliser d'espace supplémentaire?

2. Titre

Jugez s'il y a un anneau dans une liste, si c'est le cas, revenez au point de départ de l'anneau sinon, retournez Aucun

3. Idées

Si vous jugez simplement s'il y a une sonnerie, vous pouvez faire avancer le pointeur rapide deux pas à la fois et le pointeur lent un pas à la fois. Tant que les deux pointeurs sont égaux, il y a un anneau.
Mais si vous avez besoin de trouver le point de départ de l'anneau, vous devez l'analyser. (La photo vient de Nan Guo Ziqi, merci beaucoup)
image
Tout d'abord, adoptez l'idée de deux étapes plus rapides et une étape plus lente, de sorte que les deux pointeurs se rencontrent pour déterminer s'il y a un anneau, qui est le point de rencontre sur l'image. Au moment de la réunion, le pointeur lent parcourt une distance de k + M tandis que le pointeur rapide parcourt k + M + n La distance de L, n est le nombre de tours à parcourir.
2 (k + M) = k + M + n
L
k = n * L - M
Donc, après la réunion, remettez le pointeur lent sur la tête, et le pointeur rapide reste au point de rencontre pour représenter la distance soustraite M. Après cela, les pointeurs rapides et lents sont suivis étape par étape. Lorsque les deux pointeurs se rencontrent, c'est le point de départ.

4. Code

# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def detectCycle(self, head): ''' :type head: ListNode :rtype: ListNode ''' if head==None or head.next==None: return None f=s=head while f and f.next: f=f.next.next s=s.next if f==s: break if f==s: s=head while f!=s: f=f.next s=s.next return s return None

5. Référence

https://www.cnblogs.com/zuoyuan/p/3701877.html