Dairesel Bağlı Liste Problemlerinde Döngü Girişini Bulma Yöntemi

Bağlı listelerde en sık karşılaşılan problemlerden biri, listenin içinde oluşan döngünün başlangıç noktasını belirlemektir. Bu durum, özellikle bellek yönetimi ve performans optimizasyonu gerektiren yazılımlarda kritik önem taşır. Döngü tespitinde en bilinen ve verimli yöntemlerden biri olan Floyd’un Döngü Algoritması (Tortoise ve Hare olarak da bilinir), hem zaman hem de bellek açısından üstünlük sağlar.

Döngü Tespitinin Önemi ve Temel Yaklaşımlar

Döngüler, bağlı listelerde beklenmedik davranışlara yol açabilir ve bu durum, bellek sızıntılarından performans kaybına kadar çeşitli sorunlara neden olabilir. Bu nedenle, döngülerin erken tespiti ve başlangıç noktalarının belirlenmesi, yazılım geliştiriciler için olmazsa olmaz bir yetkinliktir.

İki temel yaklaşım bulunmaktadır:

• Brute Force Yöntemi: Her düğümü ziyaret ederken, daha önce görülen düğümleri kaydetmek için bir HashSet kullanılır. Bu yöntem, O(N) zaman karmaşıklığına sahiptir ancak O(N) bellek gerektirir.
• Optimize Edilmiş Yöntem: Floyd’un algoritması, sadece O(1) bellek kullanarak aynı işi gerçekleştirir.

Floyd’un Algoritmasının Çalışma Prensibi

Floyd’un algoritması, iki farklı hızda hareket eden iki gösterici kullanır: biri tek adım (yavaş), diğeri iki adım (hızlı) atar. Eğer bir döngü varsa, bu göstericiler bir noktada birbirlerine yaklaşmaya başlar ve sonunda aynı düğümde buluşurlar. Bu buluşma noktası, döngünün içinde yer alır ancak henüz döngünün başlangıcını göstermemektedir.

Algoritmanın ikinci aşamasında, yavaş gösterici başa alınır ve her iki gösterici de tek adım atarak ilerlemeye devam eder. Bu sayede, her iki gösterici de döngünün başlangıç noktasında bir araya gelir.

Matematiksel Kanıt ve Formülleştirme

Algoritmanın doğruluğunu anlamak için matematiksel bir kanıt gereklidir. Döngünün başlangıcından önceki mesafeyi L, döngüdeki mesafeyi C ve kalan döngü uzunluğunu R olarak tanımlayalım. Yavaş ve hızlı göstericilerin buluşma noktasına kadar kat ettikleri mesafeler şu şekilde ifade edilir:

• Yavaş gösterici: L + C
• Hızlı gösterici: L + C + n(C + R) (n, tam sayıdır)

Hızlı gösterici yavaş göstericinin iki katı hızda hareket ettiğinden:

2(L + C) = L + C + n(C + R) => L + C = n(C + R) => L = n(C + R) - C

Bu denklem, L’nin (n-1)(C+R) + R’ye eşit olduğunu gösterir. Bu da, yavaş göstericiyi başa alıp her iki göstericiyi de tek adım atarak ilerlettiğimizde, onların döngünün başlangıç noktasında buluşacağını kanıtlar.

Adım Adım Uygulama Örneği

Daha iyi anlaşılması için basit bir örnek üzerinden ilerleyelim. Diyelim ki elimizde aşağıdaki bağlı liste var:

3 -> 2 -> 0 -> -4
     ^        |
     |________|

Bu listede döngü, düğüm 2 adresinde başlar. Algoritmayı adım adım uygulayalım:

1. Döngü Tespiti Aşaması:

• Yavaş ve hızlı göstericiler başlangıçta aynı düğümde (3) bulunur.
• İlk adımda yavaş gösterici 2’ye, hızlı gösterici 0’a ilerler.
• İkinci adımda yavaş gösterici 0’a, hızlı gösterici -4’e ilerler.
• Üçüncü adımda yavaş gösterici -4’e, hızlı gösterici 2’ye ilerler.
• Dördüncü adımda her iki gösterici de -4’te buluşur.

1. Döngü Başlangıcını Bulma Aşaması:

• Yavaş göstericiyi başa (3) alırız.
• Her iki göstericiyi de tek adım atarak ilerletiriz.
• Birinci adımda yavaş gösterici 2’ye, hızlı gösterici 0’a ilerler.
• İkinci adımda her iki gösterici de 2’de buluşur.

Sonuç olarak, döngünün başlangıç noktasının düğüm 2 olduğu anlaşılır.

Java İle Uygulama ve Kod Örneği

Floyd’un algoritmasını Java ile uygularken, aşağıdaki adımlar izlenir:

public class DöngüBaşlangıcıBulucu {
    public ListNode döngüBaşlangıcıBul(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }

        ListNode yavaş = head;
        ListNode hızlı = head;

        // Döngü tespiti
        while (hızlı != null && hızlı.next != null) {
            yavaş = yavaş.next;
            hızlı = hızlı.next.next;

            if (yavaş == hızlı) {
                // Döngü başlangıcı bulunuyor
                yavaş = head;
                while (yavaş != hızlı) {
                    yavaş = yavaş.next;
                    hızlı = hızlı.next;
                }
                return yavaş;
            }
        }
        return null;
    }
}

Karmaşıklık Analizi ve Performans Değerlendirmesi

Floyd’un algoritmasının zaman ve bellek karmaşıklığı aşağıdaki gibidir:

• Döngü Tespiti: O(N) zaman, O(1) bellek
• Döngü Başlangıcı Bulma: O(N) zaman, O(1) bellek

Toplamda, algoritma O(N) zaman karmaşıklığına ve O(1) bellek karmaşıklığına sahiptir. Bu da, brute force yöntemlerine kıyasla önemli bir avantaj sağlar.

Mülakatlarda Kullanılabilecek Özet Cümle

Mülakatlarda karşılaşabileceğiniz bir soruya yanıt olarak, algoritmayı şu şekilde özetleyebilirsiniz:

"Floyd’un Döngü Algoritmasını kullanırım. Öncelikle yavaş ve hızlı göstericilerle bir döngü olup olmadığını kontrol ederim. Eğer döngü varsa, yavaş göstericiyi başa alıp her iki göstericiyi de tek adım atarak ilerleterek, onların döngünün başlangıç noktasında buluşmasını sağlarım. Bu yöntem, hem O(N) zaman hem de O(1) bellek kullanımıyla optimum bir çözüm sunar."

Diğer Uygulama Alanları ve Örnekler

Floyd’un algoritması, sadece bağlı listelerdeki döngülerin tespitiyle sınırlı değildir. Aynı prensip, aşağıdaki durumlarda da kullanılabilir:

• Mutlu Sayı Problemi: Bir sayının sürekli kareleri alındığında 1’e ulaşma sürecindeki döngüyü tespit etmek.
• Dizi Döngüsü Problemleri: Dairesel dizilerde tekrarlanan algoritmaları optimize etmek.
• Çakışan Dizi Problemleri: Bir dizideki tekrarlanan sayıları bulmak.

Bu algoritma, yazılım geliştiricilerin karşılaşabileceği birçok problemin çözümünde temel bir araç olarak kullanılmaktadır.