[PYTHON] Algorithme Gymnastique 21 Cycle LinkedList

LinkedList Cycle

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

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()