Bağlı listede döngü tespiti

Problem

Tek yönlü bir bağlı listenin baş düğümü veriliyor. Listede bir döngü var mı? Yani next bağlantılarını takip ederken bir düğüme ikinci kez ulaşılıyor mu? Döngü varsa true, liste null ile bitiyorsa false döndür. Listeyi değiştirmeden ve mümkünse O(1) ek bellekle çöz.

Girdi:  3 -> 2 -> 0 -> -4
             ^          |
             +----------+      (son düğüm 2'yi gösteriyor)
Çıktı:  true

Girdi:  3 -> 2 -> 0 -> -4 -> null
Çıktı:  false

Netleştirme soruları

• Liste boş olabilir mi? Tek düğüm kendisini gösterebilir mi?
• Listeyi değiştirebilir miyim (düğümleri işaretlemek, next'i bozmak)? (Genelde hayır.)
• Düğüm değerleri benzersiz mi? (Değil; bu yüzden değer karşılaştırması yetmez.)
• Sadece var/yok mu, yoksa döngünün başladığı düğüm de mi isteniyor?

İpuçları

Yaklaşım

Brute force, ziyaret kümesi: Listeyi gezerken her düğümü bir HashSet<ListNode>'a ekle; add false dönerse döngü var. O(n) zaman, O(n) bellek. ListNode equals/hashCode'u override etmediği için set kimlik (referans) bazlı çalışır; bu doğru davranıştır. Değerleri set'e koymak yanlış olur: farklı düğümler aynı değeri taşıyabilir.

Listeyi bozmak: Ziyaret edilen düğümlerin next'ini özel bir sentinel'e çevirmek O(1) bellekle çalışır ama girdiyi yok eder; neredeyse her zaman kabul edilemez.

Optimal, Floyd'un tavşan ve kaplumbağa algoritması: slow her adımda 1, fast 2 düğüm ilerler.

• Döngü yoksa fast listenin sonuna ulaşır (fast == null ya da fast.next == null) ve false döneriz.
• Döngü varsa, slow döngüye girdikten sonra iki işaretçi de döngünün içindedir. Her adımda fast, slow'a göre bir düğüm yaklaşır; aradaki mesafe d ise d adımda sıfırlanır. Mesafe birer birer azaldığı için fast, slow'un "üzerinden atlayamaz". slow döngüye girdikten sonra en fazla döngü uzunluğu kadar adımda buluşurlar.

Döngü koşulundaki fast != null && fast.next != null sırası önemli: fast.next.next'e erişmeden önce iki referansın da null olmadığından emin olmak gerekir. &&'nin kısa devre davranışı burada NullPointerException'ı önler.

Java çözümü

public final class LinkedListCycle {

    static final class ListNode {
        int val;
        ListNode next;

        ListNode(int val) { this.val = val; }
    }

    // Floyd: yavaş 1, hızlı 2 adım; döngü varsa hızlı, yavaşa içeride mutlaka yetişir
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {                                    // referans eşitliği: aynı düğüm
                return true;
            }
        }
        return false;                                              // hızlı işaretçi listenin sonuna ulaştı
    }
}

Karmaşıklık

• Zaman: O(n). Döngü yoksa fast n/2 adımda biter. Döngü varsa slow döngüye en fazla n adımda girer ve buluşma en fazla döngü uzunluğu kadar ek adım alır.
• Bellek: O(1).
• HashSet versiyonu: O(n) zaman, O(n) bellek.

Kenar durumlar ve testler

main içinde derlenip çalıştırıldı. Rastgele test yerine kapsamlı test yapıldı: 1-60 düğümlü her liste uzunluğu için döngüsüz durum ve son düğümün her olası konuma bağlandığı tüm döngülü durumlar denendi (1.800'ü aşkın kombinasyon).

Mülakatçı için

Floyd algoritmasını çoğu aday ezbere bilir; bu yüzden asıl sinyal neden çalıştığını (hızlı neden yavaşı atlamaz, neden O(n)) açıklayabilmesidir. HashSet çözümüyle başlayan aday hata yapmış sayılmaz; O(1) bellek şartını o zaman verirsin. Değerleri karşılaştıran aday (slow.val == fast.val) ciddi bir kavram hatası yapıyor: aynı değerli listeyle testini iste.

İpucu zamanlaması: İpucu genelde gerekmez. Aday HashSet ile bitirirse ikinci ipucunu ver. Floyd'u yazıp açıklayamıyorsa "hızlı işaretçi 3 adım atsaydı yine çalışır mıydı?" diye sor. Doğru cevap: ikisi de baştan başladığı sürece evet. t adımdan sonra hızlı olan yavaştan 2t düğüm öndedir; t kuyruktan uzun ve döngü uzunluğunun katı olduğunda bu fark sıfırlanır (1-11 uzunluklu döngüler ve 0-9 uzunluklu kuyruklarla simülasyonla da doğrulandı). Ama buluşma gecikebilir ve her adımda daha çok düğüm okunur. İşaretçiler farklı düğümlerden başlasaydı, göreli hızı 2 olan bir çift, çift uzunluklu bir döngüde tek mesafeyle hiç buluşmayabilirdi; 2 adımın tercih edilmesinin nedeni göreli hızın 1 olması ve mesafenin birer birer azalmasıdır. Aranan, adayın bu göreli hız argümanını kurabilmesi.

Takip soruları:

1. Döngünün başladığı düğümü bul. (Beklenen: buluşmadan sonra bir işaretçiyi başa al, ikisini birer adım ilerlet; buluştukları yer döngü başı. Matematiği: baştan döngü başına uzaklık, buluşma noktasından döngü başına uzaklığa döngü uzunluğu modunda eşit. LeetCode 142.)
2. Döngünün uzunluğunu bul. (Beklenen: buluşma noktasından bir işaretçiyi döndürüp aynı düğüme dönene kadar say.)
3. Bu fikir bağlı liste dışında nerede kullanılır? (Beklenen: tekrar eden sayıyı bulma, LeetCode 287; rastgele sayı üreteci periyodu; Pollard'ın rho algoritması; mikroservis çağrı zincirinde döngü tespiti için ise genelde ziyaret listesi ya da hop sayacı tercih edilir.)

Benzer problemler

• Linked List Cycle II (LeetCode 142).
• Find the Duplicate Number (LeetCode 287): diziyi örtük bağlı liste olarak görmek.
• Happy Number (LeetCode 202): sayı dizisinde döngü.
• Middle of the Linked List (LeetCode 876): hızlı/yavaş işaretçi.
• Reverse Linked List (LeetCode 206) (bu sette: reverse-linked-list).