JS ALGORITHMS
Linked List (Bağlı Liste) Detect Loop (Döngüsel Yapıları Bulma)
Bir önceki yazımızda Linked List (Bağlantılı Listeleri) ve bunların Circular olup olmadığını nasıl kontrol ettiğimizi anlatmıştım. Bu yazıda da herhangi bir düğümden daha önceki düğümlere bir bağlantı yapılıp herhangi bir yerde döngüye neden olmuş mu diye bakacağız.
Bu yazının bir önceki yazıdan farklı olarak son düğüm noktasının Head bağlantı yaparak işlemleri gerçekleştirmiştik.
Head link oluşturmadığı, herhangi bir düğüme link oluşturduğu durumlarda bu kontrolü Head göre yapamıyor olacağız. Bu durumda nasıl bir algoritma yazmalıyız ?
Burda bir önceki yazıda kullandığımız algoritmayı kullandığımız taktirde Head ile kontrol olmadığı için sonsuz döngüye girecektir. Bunu çözmek için Cyclic Loop algılayan 3 türde algoritma yazabiliriz.
- Gezdiğimiz Düğümleri veya Hashlarini Bir Store saklayarak buradan sorgulama
- Düğümlere ek flag ekleyerek. Yeri geldiği zaman bu flag kontrol etmek.
- Floyd Methodunu kullanmak.
isCyclic_SolveWithStore
Düğümlerin üzerinde gezerken düğümleri Set içerisinde saklayıp daha sonra buradan sorgulama yapıyoruz.
isCyclic_SolveWithExtraFlag
Düğümlerin içerisine bir flag ekleyerek gezdiğimiz düğümleri işaretliyoruz. Iterator üzerinden bir daha geçerse düğüm işaretlenmiş mi diye bakıyor.
isCyclic_SolveWithFloydMethod
Bir tane standart iterator dışında bir tanede 2 adım atabilen hızlı iterator oluşturuyoruz. Eğer bir yerlerde döngü varsa hızlı olanın, yavaş olan yetişmesini bekliyoruz.
Kaynak
Okumaya Devam Et 😃
Bu yazının devamı veya yazı grubundaki diğer yazılara erişmek için bu linke tıklayabilirsiniz.
