Cycle Detection

Giriş
Sanırım en çok kullanılan algoritma Floyd'un algoritması

Floyd’s Cycle Detection Algorithm

1. hasCycle problemi

Leetcode 141. Linked List Cycle Floyd's Cycle Detection algoritmasını kullanıyor.

Bu algoritmada slow ve fast isimli iki tane pointer tanımlanıyor. Slow birer birer ilerletilirken, fast ikişer ikişer ilerletiliyor. Slow ve Fast döngünün başladığı noktadan biraz ileride bir yerde buluşuyorlar.

Burada da bir soru var.

Örnek - C++

Şöyle yaparız

bool hasCycle(ListNode *head) {
  if(head == NULL || head -> next == NULL) //Liste boş veya tek elemanlı
    return false;

  ListNode *fast = head;
  ListNode *slow = head;

  while(fast -> next && fast -> next -> next){ //Listenin sonuna geldik mi
    fast = fast -> next -> next; //İki adım ilerle
    slow = slow -> next; //Bir adım ilerle
    if(fast == slow)
      return true;
  }
  return false;
}

Örnek

Şöyle yaparız. Bu kodu okuması daha kolay

bool floyd(Node* head) {
    Node* tortoise = head;
    Node* hare = head;
    while (hare != NULL && hare->next != NULL) {
        tortoise = tortoise->next;
        hare = hare->next->next;
        if (tortoise == hare) {
            return true;
        }
    }
    return false;
}

2. start of Cycle problemi

142. Linked List Cycle II Floyd's Cycle Detection algoritmasını kullanıyor. Burada cycle'ın başladığı düğümü bulmamız isteniyor. Aslında çözüm bir denkleme dayanıyor. Bu denklemin şeklen gösterimi burada

Örnek

Şöyle yaparız. 

// Keep the hare at the meeting point
tortoise = head;
while (tortoise != hare) {
    tortoise = tortoise->next;
    hare = hare->next;
}
Node* cycleStart = tortoise;

Örnek

Şöyle yaparız. Çözümde buluşma noktasındaki pointer birer birer ilerletiliyor. Yeni slow pointer'da listenin başından başlayarak ilerletiliyor. Buluştukları nokta döngünün başladığı yer.