K18
Listede Döngü Tespiti
Teknik Tanım & Görev
Baş düğümden yürüyünce bir düğüme ikinci kez geliniyor mu, belirleyin.
Düğüm biçimi: dugumler[i] = [değer, sonraki_indeks]. sonraki_indeks == -1 listenin sonudur. bas, baş düğümün indeksidir; boş liste için -1. Düğümler bağlantı sırasında dizilmek zorunda değildir. Ham dizi üzerinde dilimleme, ters çevirme veya sorted() bağlantı sırasını vermez.
pos parametresi yoktur. Döngü yalnızca sonraki indekslerindedir. Baştan ERİŞİLEMEYEN bir düğümün oluşturduğu döngü sayılmaz: cevap, yalnız bas'tan çıkan zincire bakılarak verilir. Floyd'un yavaş/hızlı gösterici yöntemi beklenir.
Fonksiyon İmzası (Python)
dongu_var_mi(dugumler: list[list[int]], bas: int) -> boolGirdi ve Çıktı Sözleşmesi
Çıktı Kuralı:True: bas'tan başlayan yürüyüş bir düğüme yeniden girer. False: zincir -1 ile biter. Erişilmeyen döngü False'tur.
Sistem Kısıtları (Constraints)
0 <= dugumler.length <= 10^4
-10^4 <= değer <= 10^4
bas, geçerli bir indeks veya -1
sonraki_indeks, -1 veya 0..n-1 aralığındadırÖrnek Yürütme Analizi
dugumler = [[3,1],[2,2],[0,3],[-4,1]], bas = 0
0→1→2→3→1 döngüsü. Cevap True.
dugumler = [[1,1],[2,-1],[9,3],[8,2]], bas = 0
Baştan giden zincir 0→1→son. İndeks 2 ve 3 kendi aralarında döner ama baştan erişilmez.
Cevap False. Tüm sonraki alanlarını tarayan çözüm bunu yanlışlıkla True sayar.Örnek Test Senaryoları (3)
Örnek 1: Döngü Var
Girdi:
[[[3,1],[2,2],[0,3],[-4,1]],0]Beklenen Çıktı:
trueÖrnek 2: İki Düğümlü Döngü
Girdi:
[[[1,1],[2,0]],0]Beklenen Çıktı:
trueÖrnek 3: Döngü Yok
Girdi:
[[[1,-1]],0]Beklenen Çıktı:
false