[PYTHON] Algorithmus Gymnastik 21 LinkedList-Zyklus

LinkedList Cycle

Schreiben Sie wie in der Abbildung oben gezeigt eine Funktion, die bestimmt, ob LinkedList ein Zyklus ist.

Solution Verwenden Sie langsame und schnelle Zeiger, um die LinkedList zu durchlaufen. Bei jeder Iteration bewegt sich der langsame Zeiger um einen Schritt und der schnelle Zeiger um zwei Schritte.

Wenn es keinen Zyklus gibt, erhalten Sie zwei Ergebnisse.

1. Wenn die LinkedList keine Zyklen hat, erreicht der schnelle Zeiger das Ende der LinkedList vor dem langsamen Zeiger, was darauf hinweist, dass die LinkedList keine Zyklen hat.
2. Wenn die LinkedList keine Zyklen hat, kann der langsame Zeiger den schnellen Zeiger nicht einholen.

Wenn die LinkedList Zyklen enthält, geht der schnelle Zeiger zuerst in den Zyklus, gefolgt vom langsamen Zeiger. Danach bewegen sich beide Zeiger im Zyklus unbegrenzt weiter. Wenn Sie diese beiden Zeiger zu irgendeinem Zeitpunkt treffen, können Sie daraus schließen, dass die LinkedList einen Zyklus enthält. Lassen Sie uns analysieren, ob sich die beiden Zeiger treffen können. Es gibt zwei Möglichkeiten, wenn sich der schnelle Zeiger von hinten dem langsamen Zeiger nähert.

1. Der schnelle Zeiger befindet sich eins hinter dem langsamen Zeiger.
2. Der schnelle Zeiger befindet sich zwei hinter dem langsamen Zeiger.

Alle anderen Abstände zwischen den schnellen und langsamen Zeigern ergeben eine dieser beiden Möglichkeiten. Lassen Sie uns diese Szenarien analysieren, wobei wir berücksichtigen, dass sich der schnelle Zeiger immer zuerst bewegt.

1. Wenn der schnelle Zeiger einen Schritt hinter dem langsamen Zeiger liegt: Der schnelle Zeiger bewegt sich zwei Schritte, der langsame Zeiger bewegt sich einen Schritt und beide treffen sich.
2. Wenn der schnelle Zeiger zwei Schritte hinter dem langsamen Zeiger liegt: Der schnelle Zeiger bewegt sich zwei Schritte und der langsame Zeiger bewegt sich einen Schritt. Nach dem Verschieben befindet sich der schnelle Zeiger hinter dem langsamen Zeiger, und dieses Szenario führt zum ersten Szenario.

Demo

Implementierung

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