Algorithme Gymnastique 21 Cycle LinkedList

LinkedList Cycle

Screen Shot 2020-08-04 at 23.00.15.png

Comme le montre l'image ci-dessus, écrivez une fonction qui détermine si LinkedList est un cycle.

Solution Utilisez des pointeurs lents et rapides pour parcourir la LinkedList. À chaque itération, le pointeur lent se déplace d'un pas et le pointeur rapide se déplace de deux pas.

S'il n'y a pas de cycle, vous obtiendrez deux résultats.

  1. Si LinkedList n'a aucun cycle, le pointeur rapide atteint la fin de LinkedList avant le pointeur lent, indiquant que LinkedList n'a pas de cycles.
  2. Si LinkedList n'a pas de cycles, le pointeur lent ne peut pas rattraper le pointeur rapide.

Si LinkedList a des cycles, le pointeur rapide entre d'abord dans le cycle, suivi du pointeur lent. Après cela, les deux pointeurs continuent à se déplacer indéfiniment dans le cycle. Si vous rencontrez ces deux pointeurs à un stade quelconque, vous pouvez conclure qu'il existe un cycle dans la LinkedList. Analysons si les deux pointeurs peuvent se rencontrer. Il existe deux possibilités lorsque le pointeur rapide s'approche du pointeur lent par l'arrière.

  1. Le pointeur rapide est situé derrière le pointeur lent.
  2. Le pointeur rapide est situé deux derrière le pointeur lent.

Toutes les autres distances entre les pointeurs rapide et lent se traduisent par l'une de ces deux possibilités. Analysons ces scénarios, en considérant que le pointeur rapide se déplace toujours en premier.

  1. Si le pointeur rapide est un pas derrière le pointeur lent: le pointeur rapide se déplace de deux pas, le pointeur lent se déplace d'un pas et les deux se rencontrent.
  2. Si le pointeur rapide est à deux pas derrière le pointeur lent: le pointeur rapide se déplace de deux pas et le pointeur lent se déplace d'un pas. Après le déplacement, le pointeur rapide sera un derrière le pointeur lent et ce scénario entraînera le premier scénario.

démo

Screen Shot 2020-08-04 at 23.19.07.png

la mise en oeuvre

class Node:
  def __init__(self, value, next=None):
    self.value = value
    self.next = next

def has_cycle(head):
  # time complexity O(n)
  # space complexity O(1)
  fast, slow = head, head
  while fast is not None and slow is not None:
    fast = fast.next.next
    slow = slow.next
    if fast == slow:
      return True
  return False


def main():
  head = Node(1)
  head.next = Node(2)
  head.next.next = Node(3)
  head.next.next.next = Node(4)
  head.next.next.next.next = Node(5)
  head.next.next.next.next.next = Node(6)
  print("LinkedList has cycle: " + str(has_cycle(head)))

  head.next.next.next.next.next.next = head.next.next
  print("LinkedList has cycle: " + str(has_cycle(head)))

  head.next.next.next.next.next.next = head.next.next.next
  print("LinkedList has cycle: " + str(has_cycle(head)))


main()

Recommended Posts

Algorithme Gymnastique 21 Cycle LinkedList
Gymnastique algorithmique 12
Gymnastique algorithmique 10
Gymnastique algorithmique 9
Gymnastique algorithmique 14
Gymnastique algorithmique 2
Gymnastique algorithmique 7
Gymnastique algorithmique 15
Gymnastique algorithmique 16
Gymnastique algorithmique 8
Gymnastique algorithmique 17
Gymnastique algorithmique 18
Gymnastique algorithmique 11
Exercice d'algorithme 5
Gymnastique algorithmique 4
Gymnastique algorithmique 24 sous-ensembles
Gymnastique algorithmique 23 Intervalles de fusion
Gymnastique d'algorithme 20 Supprimer les doublons
Algorithme Gymnastique 24 Tri cyclique
Gymnastique d'algorithme 19 Sous-chaîne sans répétition
Gymnastique algorithmique 24 Inverser une liste liée
Gymnastique d'algorithme 20 paires avec somme cible
Gymnastique algorithmique 22 Mise au carré d'un tableau trié
Gymnastique algorithmique 24 Milieu de la liste liée