K18

Listede Döngü Tespiti

Temel Seviye (Junior)
Hedef Süre: 15 - 20 Dakika
Tip: BOOLEAN

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

Girdi 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
Python Editörü Yükleniyor...
Girdi Parametreleri
[
  [
    [
      3,
      1
    ],
    [
      2,
      2
    ],
    [
      0,
      3
    ],
    [
      -4,
      1
    ]
  ],
  0
]
Beklenen Çıktı
true