Middle of the Linked List
Aynı uzunlukta iki dizide saklanan tek yönlü bağlı bir liste veriliyor. i düğümü values[i] değerini tutar ve next[i] düğümüne bağlanır; -1 listeyi sonlandırır ve baş düğüm 0 numaralı düğümdür. Düğümler liste sırasına göre saklanmadığından bağlantıları izleyin.
Ortadaki düğümün değerini döndürün. Listede çift sayıda düğüm varsa iki orta düğüm bulunur; ikincisinin değerini döndürün.
Fonksiyon
- valuesinteger-array
- her düğümde tutulan değer
- nextinteger-array
- her düğümün bağlantı verdiği düğümün indeksi veya son düğüm için -1
- Döndürürinteger
- orta düğümün değeri; uzunluk çift olduğunda ikinci orta düğümün değeri
Kısıtlar
1 ≤ n ≤ 5000; buradan,valuesvenextdizilerinin uzunluğudur.-104 ≤ values[i] ≤ 104- Her bir
next[i],-1ya da0ilen-1arasında bir düğüm indeksidir. -
0düğümünden başlayarak liste her düğümü tam olarak bir kez ziyaret eder ve ardından-1değerine ulaşır. Döngü yoktur.
Örnekler
- Girdi
- values = [4, 9, 2, 7, 5]next = [3, -1, 1, 4, 2]
- Çıktı
- 5
- Açıklama
0düğümünden bağlantıları takip etmek0, 3, 4, 2, 1düğümlerini verir; dolayısıyla liste4, 7, 5, 2, 9şeklindedir. Beş düğümün üçüncüsü, değeri5olan4düğümüdür. Dizinin kendi orta girdisi olanvalues[2] = 2ise farklı bir düğümdür.
- Girdi
- values = [10, 20, 30, 40, 50, 60]next = [1, 2, 3, 4, 5, -1]
- Çıktı
- 40
- Açıklama
- Burada düğümler sıralı olarak saklanır. Altı düğümde ortada iki düğüm vardır:
30ve40; ikinci olan seçilir.
- Girdi
- values = [8]next = [-1]
- Çıktı
- 8
- Açıklama
- Tek düğümlü bir listenin ortası kendisidir.
Gönderirken +13 gizli test
Ek soru
Liste boyunca tek geçişte, listenin üçte biri kadar aşağıdaki düğümü döndürebilir misin? Her işaretçi ne kadar hızlı ilerlerdi ve nerede dururdun?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Listenin uzunluğunu, sonuna ulaşana kadar bilemezsiniz. Ya iki yürüyen de listenin başından başlasa ve biri diğerinden iki kat hızlı ilerleseydi?
Daha hızlı yürüyen sona ulaştığında, daha yavaş olan mesafenin yarısını katetmiş olur; dolayısıyla ortadaki düğümde durur. Geriye kalan tek ayrıntı, çift uzunluklu bir listenin ikinci orta düğümünde bitmesi için ne zaman durulacağıdır.
slowvefastdeğişkenlerini0düğümünde başlat.fast,-1olmadığı venext[fast],-1olmadığı süreceslowdeğişkenini bir bağlantı,fastdeğişkenini iki bağlantı ilerlet. Ardındanvalues[slow]değerini döndür.
Çözüm
Bir dizide orta nokta n / 2 indeksindedir. Bağlı listede indeks yoktur: Listenin uzunluğunu ancak sonuna kadar ilerleyerek öğrenebilirsiniz; o noktaya geldiğinizde orta noktayı geçmiş olursunuz. Listeyi bir diziye kopyalayabilir ya da önce sayıp sonra yeniden ilerleyebilirsiniz. Pratik çözümde iki işaretçi liste boyunca farklı hızlarda ilerler; hızlı olanın yolu bittiğinde yavaş olan yarı yolu tamamlamış olur.
D değerlerini bir diziye kopyalayın
Sezgi
Bu problemde bir işaretçi, düğüm indeksidir. Sonraki düğüme geçmek için node = next[node] kullanılır ve -1 değerine ulaşmak listenin sonuna geldiğiniz anlamına gelir. İlk örnekte, 0 düğümünden başlayan gezinme 0 → 3 → 4 → 2 → 1 → -1 şeklindedir.
Listenin sorunu, bir konuma doğrudan atlayamamanızdır. Bu yüzden onu atlayabileceğiniz bir yapıya dönüştürün: Listeyi bir kez gezin ve ilerlerken her değeri yeni bir diziye ekleyin. Bu dizi, değerleri liste sırasıyla tutar; ilk örnekte [4, 7, 5, 2, 9] olur ve orta elemanı, tam sayı bölmesiyle length / 2 indeksindedir.
Bu indeks, çift uzunluk için ikinci ortadaki elemanı kendiliğinden verir: altı değer, 3 indeksini yani ikinci örnekte 40 olan dördüncü değeri verir. Gezinme O(n) zaman, kopyalama ise sonraki iki yaklaşımın önlediği O(n) ek bellek gerektirir.
Algoritma
- Boş bir diziyle ve
node = 0ile başla. node,-1olmadığı sürecevalues[node]değerini ekle venext[node]konumuna ilerle.- Aşağı yuvarlanmış
length / 2indeksindeki girdiyi döndür.
def middleNode(values, next):
in_order = []
node = 0
while node != -1:
in_order.append(values[node])
node = next[node]
return in_order[len(in_order) // 2]Say, sonra yolun yarısına kadar yürü
Sezgi
Tüm kopyaya ihtiyacınız yok, yalnızca uzunluğa. Listeyi bir kez dolaşıp düğümleri sayın. Ardından baştan tekrar başlayıp length / 2 adım atın ve aşağı yuvarlayın. Durduğunuz düğüm ortadaki düğümdür.
Neden bu kadar adım atıyoruz: k adımdan sonra, başı 0 konumunda sayarak k konumundaki düğümde olursunuz. 5 elemanlı bir listenin ortası 2 konumudur; 6 elemanlı bir listenin ikinci ortası ise 3 konumudur. Her ikisi de length / 2 değerine eşittir. İlk örnekte 5 sayar, iki adım atar 0 → 3 → 4 ve values[4] = 5 değerini okursunuz.
Bellek kullanımı artık O(1). Bunun karşılığında listenin yarısında ikinci kez ilerlersiniz; toplamda 1.5n hareket eder, bu da hâlâ O(n) değerindedir.
Algoritma
0düğümünden-1düğümüne kadar ilerleyip düğümleri say.0düğümüne geri dön.node = next[node]işlemini, aşağı yuvarlanmışcount / 2sayısı kadar tekrarla.values[node]değerini döndür.
def middleNode(values, next):
length = 0
node = 0
while node != -1:
length += 1
node = next[node]
node = 0
for _ in range(length // 2):
node = next[node]
return values[node]Hızlı ve yavaş işaretçiler
Sezgi
İki işaretçiyi başa yerleştir. Her turda slow bir düğüm, fast ise iki düğüm ilerler. k turdan sonra slow k konumunda, fast ise 2k konumundadır; dolayısıyla slow, fast'in aldığı mesafenin her zaman yarısını katetmiştir. Fast sona ulaştığında slow ortadadır ve uzunluğu bilmen gerekmez.
Durdurma kuralı, hangi orta düğümü bulacağını belirler. Fast gerçek bir düğüm olduğu ve ardından bir düğüm daha bulunduğu sürece devam et: fast != -1 ve next[fast] != -1. Uzunluk tekse fast son düğümde durur. Uzunluk çiftse fast sondan çıkarak -1 konumuna geçer ve bu da slow'u bir adım daha ilerletip ikinci orta düğüme getirir. İkinci örnekte slow 0, 1, 2, 3 boyunca ilerlerken fast 0, 2, 4, -1 boyunca ilerler ve values[3] değeri 40 olur.
İlk örnekte slow 0, 3, 4 düğümlerini, fast ise 0, 4, 1 düğümlerini ziyaret eder; 1 son düğüm olduğundan döngü, slow 4. düğümdeyken durur ve yanıt 5 olur. Fast yaklaşık n adım, slow ise n / 2 adım ilerler; bu işlem tek geçişte ve iki tamsayı bellek kullanılarak yapılır.
Algoritma
slow = 0vefast = 0olarak ayarlayın.fast != -1venext[fast] != -1olduğu süreceslow = next[slow]vefast = next[next[fast]]olarak ayarlayın.values[slow]değerini döndürün.
def middleNode(values, next):
slow = fast = 0
# Stop when fast is on the last node or has stepped past it.
while fast != -1 and next[fast] != -1:
slow = next[slow]
fast = next[next[fast]]
return values[slow]
Tuzaklar ve uç durumlar
Döngü kısadır; bu nedenle hatalar, nerede başladığında, nerede durduğunda ve ne döndürdüğünde ortaya çıkar.
values[n / 2]döndürmek. Düğümler liste sırasına göre saklanmaz, bu yüzden dizinin ortadaki girdisi genellikle başka bir düğümdür. İlk örnekte5yerine2verir.- Uzunluk çift olduğunda ilk ortadakini bulmak.
next[fast]venext[next[fast]]gerçek değerler olduğu sürece çalışan bir döngü bir tur erken durur ve ikinci örnekte40yerine30döndürür. fast != -1kontrolünden öncenext[fast]değerini kontrol etmek. Uzunluk çift olduğunda fast,-1olur venext[-1]okumak çoğu dilde çökmeye neden olur. Python'da ise bunun yerine sessizce son girdi okunur; bu daha kötüdür.- Sayma yaklaşımında
count / 2 - 1adım yürümek veya yukarı yuvarlamak. Başı0konumu olarak say ve aşağı yuvarlanmışcount / 2kadar adım at. - Düğümün değeri yerine düğüm dizinini döndürmek.
- Dizilerin 1'den başladığı Lua ve R'deki ofseti unutmak. Düğüm dizinlerini 0 tabanlı tut ve
next[node + 1]değerini oku. Ruby ve R,nextsözcüğünü ayırdığından bu dillerdeki başlangıç kodunda parametreyenext_adı verilir.
Sıkça sorulan sorular4
Hızlı ve yavaş işaretçiler bağlı bir listenin ortasını nasıl bulur?
İkisi de baştan başlar ve her turda hızlı işaretçi iki düğüm ilerlerken yavaş olan bir düğüm ilerler. k turdan sonra hızlı işaretçi 2k konumunda, yavaş olan ise k konumundadır; yani tam olarak yarı mesafe kadar ilerlemiştir. Böylece hızlı işaretçi listenin sonuna ulaştığında yavaş olan listenin ortasında olur.
Bağlı bir listenin ortasını bulmanın zaman ve uzay karmaşıklığı nedir?
Üç yaklaşımın da zaman karmaşıklığı O(n)'dir; çünkü listenin yaklaşık yarısı veya daha fazlası boyunca ilerlemeden orta eleman bulunamaz. Değerleri kopyalamak O(n) ek bellek kullanır. Önce sayma yöntemi ile hızlı ve yavaş işaretçiler O(1) kullanır ve işaretçilerin yalnızca tek bir geçiş yapması yeterlidir.
İkinci orta düğüm yerine ilk orta düğümü nasıl döndürürsünüz?
Hızlı işaretçinin bir tur daha erken durması için durdurma kuralını değiştir: next[fast] != -1 ve next[next[fast]] != -1 koşulları sağlandığı sürece döngüye devam et. Altı düğüm için yavaş işaretçi, 3 yerine 2 konumunda durur. Sayma yaklaşımında count / 2 yerine (count - 1) / 2 adım ilerle.
Hızlı ve yavaş işaretçi tekniği başka nerelerde kullanılır?
Aynı iki hız, bağlı bir listedeki döngüyü tespit eder: döngüde hızlı işaretçi yavaşı turlar ve ikisi buluşur. Ayrıca döngünün nerede başladığını bulurlar ve bir listeyi birleştirme sıralaması için ya da listenin her iki yönde de aynı okunup okunmadığını kontrol etmek için ikiye bölerler.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def middleNode(values, next):
# Kodu buraya yazınDurum 1
Durum 2
Durum 3
Girdi
values = [4, 9, 2, 7, 5] next = [3, -1, 1, 4, 2]
Beklenen
5