Linked List Cycle
Bağlı liste next dizisinde saklanır: i düğümü next[i] düğümüne bağlanır ve -1 listenin orada bittiği anlamına gelir. Baş düğüm 0'dır. Baş düğümden başlayarak bağlantıları takip et ve daha önce ziyaret ettiğin bir düğüme yeniden ulaşırsan true, listenin sonuna ulaşırsan false döndür. İzleme sırasında hiç ulaşılamayan düğümler, birbirlerine bağlanıp bir döngü oluştursalar bile hesaba katılmaz.
Fonksiyon
- nextinteger-array
- her düğümün bağlantısı: next[i], i düğümünden sonraki düğümdür veya -1'dir
- Döndürürboolean
- 0 düğümünden başlayan gezinme bir düğümü yeniden ziyaret ederse true, -1'e ulaşırsa false
Kısıtlar
1 ≤ next.length ≤ 104-1 ≤ next[i] ≤ next.length-1- Birkaç düğüm aynı düğüme bağlanabilir ve bazı düğümlere baş düğümden ulaşılamayabilir.
Örnekler
- Girdi
- next = [1, 2, 3, 1]
- Çıktı
- true
- Açıklama
- Yürüyüş 0, 1, 2, 3 şeklinde ilerler ve sonra 1'e geri döner. 1 düğümü iki kez ziyaret edilir, bu nedenle listede 1, 2 ve 3 düğümlerinden geçen bir döngü vardır.
- Girdi
- next = [2, -1, 1]
- Çıktı
- false
- Açıklama
- Yürüyüş 0, 2, 1 şeklinde ilerler ve ardından
-1'e ulaşır: üç farklı düğümden sonra sona erer, dolayısıyla döngü yoktur.
- Girdi
- next = [-1, 2, 1]
- Çıktı
- false
- Açıklama
- Node 0,
-1değerine bağlanır; bu nedenle liste bir düğüm uzunluğundadır. 1 ve 2 numaralı düğümler bir döngü içinde birbirine bağlanır, ancak baştan başlayan gezinme bu düğümlere asla ulaşmaz.
Gönderirken +16 gizli test
Ek soru
Döngünün başladığı düğümü de O(1) ek bellek kullanarak bulabilir misin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
nextişaretçisini takip ederek 0. düğümden ilerleyin. Döngüsü olmayan bir liste-1noktasında durur, ancak döngüsü olan bir liste hiç durmaz. Kendi etrafınızda döndüğünüzü fark etmek için neyi hatırlamanız gerekir?Ziyaret edilen düğümleri işaretlemek işe yarar ama her düğüm için bellek gerektirir. Bunun yerine, liste boyunca farklı hızlarda ilerleyen iki işaretçi gönderin. Liste döngüye girerse aralarındaki mesafeye ne olur?
Her turda
slowbir bağlantı,fastise iki bağlantı ilerlet.fastveyanext[fast]-1ise döngü yoktur. İki işaretçi aynı düğüme denk gelirse döngü vardır.
Çözüm
Döngüsü olmayan bir liste, n bağlantı içinde -1 değerine ulaşır; ancak döngüsü olan bir liste hiç bitmez, bu yüzden sonunu bekleyemezsin. Yürüyüşün kendi etrafında döndüğünü fark etmenin bir yoluna ihtiyacın var. Ziyaret ettiğin her düğümü hatırlamak bunu O(n) bellekle yapar. Floyd’un hızlı ve yavaş işaretçileri bunu iki tam sayı kullanarak yapar; çünkü iki kat hızlı hareket eden bir işaretçi, bir döngünün içinde yavaş olana mutlaka yetişir.
Dolaştığınız düğümleri işaretleyin
Sezgi
0 düğümünden başlayarak ilerle ve her düğümden ayrılırken onu işaretle. Zaten işaretlenmiş bir düğüme ulaşırsan, ilerleme o düğüme geri dönmüştür ve oradan sonsuza kadar tekrar eder: bu bir döngüdür. 1. örnekte 0, 1, 2 ve 3'ü işaretlersin ve 3 düğümünden çıkan bağlantı, işaretlenmiş olan 1 düğümüne gider.
Düğümler 0 ile n-1 arasında numaralandırılır; bu nedenle n uzunluğundaki bir boole dizisi, ziyaret edilen düğümlerin kümesini tutar. Nesnelerden oluşturulmuş bağlı bir listede, düğüm referanslarını bunun yerine bir hash kümesine koyarsın; fikir aynıdır.
Her düğüm en fazla bir kez işaretlenir ve ilerleme ilk tekrarda veya -1 değerinde durur; bu nedenle en fazla n adım sürer: işaretler için O(n) zaman ve O(n) bellek.
Algoritma
nuzunluğunda, tüm değerleri false olan bir boolean dizisivisitedoluşturun.node = 0olarak ayarlayın.node,-1olmadığı sürece,visited[node]zaten true isetruedöndürün.- Aksi takdirde
visited[node]değerini ayarlayın venext[node]değerine geçin. - İzlenen yol
-1değerine ulaştığındafalsedöndürün.
def hasCycle(next):
visited = [False] * len(next)
node = 0
while node != -1:
if visited[node]:
return True # back at a node already on the path
visited[node] = True
node = next[node]
return FalseHızlı ve yavaş işaretçiler (Floyd’un döngü tespiti)
Sezgi
İki işaretçiyi baştan başlat. slow her turda bir bağlantı, fast ise iki bağlantı ilerler. Liste biterse fast önce -1 değerine ulaşır ve false döndürürsün. Döngü varsa fast önce döngüye girer ve slow da ulaşana kadar dönmeye devam eder.
İkisi de döngüye girdikten sonra fast her turda slow'a tam olarak bir düğüm yaklaşır. fast'in slow'a ulaşmak için katetmesi gereken mesafe her turda bir azalır; böylece mesafe sıfıra iner ve işaretçiler aynı düğümde buluşur. Her seferinde bir düğüm ilerlediği için fast, slow'u asla atlayamaz.
1. örnekte, bir turun ardından slow 1. düğümdedir ve fast 2. düğümdedir. İki turun ardından slow 2. düğümdedir ve fast 3, 1 yolunu katetmiştir. Üç turun ardından ikisi de 3. düğümdedir; dolayısıyla yanıt true olur.
slow'un döngüye girmesi en fazla n tur sürer ve döngüye girdikten sonra bir turu tamamlamadan buluşurlar; bu nedenle zaman karmaşıklığı O(n)'dir. Kullanılan tek bellek iki düğüm numarasıdır.
Algoritma
slow = 0vefast = 0olarak ayarla.fastdeğeri-1değilken venext[fast]değeri-1değilken,slowdeğerini bir bağlantı,fastdeğerini iki bağlantı ilerlet.- Her ilerlemeden sonra aynı düğümdeyseler
truedöndür. - Döngü durduğunda,
fastsona ulaşmıştır:falsedöndür.
def hasCycle(next):
slow = 0
fast = 0
# fast needs two links to move; if either is missing, the list ends.
while fast != -1 and next[fast] != -1:
slow = next[slow]
fast = next[next[fast]]
if slow == fast:
return True
return False
Tuzaklar ve uç durumlar
Buradaki hatalar listenin sonuyla ve hangi düğümlerin sayıldığıyla ilgilidir.
- Her ikisini de kontrol etmeden
fastişaretçisini iki bağlantı ilerletmek.next[next[fast]]değerini okumadan önce hemfasthem denext[fast]gerçek düğümler olmalıdır; aksi hâldenext[-1]değerini okursunuz. Bu, çoğu dilde çökmeye neden olurken Python’da sessizce son öğeyi döndürür. - İşaretçileri ilerletmeden önce karşılaştırmak. İkisi de 0 numaralı düğümde başlar, bu yüzden döngünün başında yapılan bir kontrol her listede döngü olduğunu bildirir.
- Yürüyüş yerine dizinin tamamına bakmak.
[-1, 2, 1]içinde 1 ve 2 numaralı düğümler bir döngü oluşturur, ancak baş düğüm hemen sona erer; dolayısıyla yanıtfalseolur.nextiçinde bir değerin tekrarlanıp tekrarlanmadığını kontrol etmek de yanlıştır:[4, 4, 4, 4, -1]içinde birkaç düğüm 4 numaralı düğüme bağlanır ve döngü yoktur. - Bir döngünün mutlaka baş düğüme geri dönmesi gerektiğini varsaymak.
[1, 2, 3, 4, 4]içinde son düğüm kendisine bağlanır;[0]içinde ise bunu baş düğüm yapar.
Sıkça sorulan sorular4
Floyd'un döngü tespiti nasıl çalışır?
İki işaretçi baştan başlar: biri her adımda bir bağlantı, diğeri iki bağlantı ilerler. Döngü yoksa hızlı olan sona ulaşır. Döngü varsa ikisi de döngünün içine girer, hızlı olan her adımda aradaki mesafeyi bir düğüm azaltır ve aynı düğümde buluşurlar.
Bağlı Liste Döngüsü'nün zaman ve alan karmaşıklığı nedir?
Her iki yaklaşım da O(n) zaman alır; çünkü her düğümden sınırlı sayıda geçilir. Ziyaret edilen düğümleri işaretlemek O(n) ek bellek gerektirir. Floyd'un hızlı ve yavaş işaretçileri O(1) alan gerektirir: iki düğüm numarası.
Hızlı işaretçi neden yavaş işaretçinin üzerinden atlayamaz?
Döngünün içinde, her turda fast iki düğüm, slow ise bir düğüm ilerler; böylece fast’in slow’a ulaşmak için katetmesi gereken mesafe tam olarak bir azalır. Her turda bir azalan mesafe 3, 2, 1, 0 şeklinde ilerler ve sıfırın altına düşemez; dolayısıyla iki işaretçi bir düğümde buluşur.
Döngüyü adımları sayarak tespit edebilir misin?
Bu dizi biçiminde, evet: döngüsü olmayan bir liste n bağlantı içinde -1'e ulaşır; bu nedenle sona ulaşmadan n bağlantı boyunca ilerlemek, O(1) bellekle bir döngü olduğunu kanıtlar. Düğüm sayısına ihtiyaç duyar; işaretçilerden oluşan bir liste bu sayıyı vermez ve önce düğümleri saymak, döngü varsa asla tamamlanmaz. Floyd yöntemi saymaya gerek duymaz.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def hasCycle(next):
# Kodu buraya yazınDurum 1
Durum 2
Durum 3
Girdi
next = [1, 2, 3, 1]
Beklenen
true