Reorder List
Aynı uzunluktaki iki dizide saklanan tek yönlü bir bağlı listen var. i düğümü values[i] değerini tutar ve next[i] düğümüne bağlanır; -1 listenin sonunu belirtir ve baş düğüm 0'dır. Düğümler liste sırasına göre saklanmadığından bağlantıları takip et.
Liste sırasındaki düğümlere L0, L1, ..., Lk adını ver. Listeyi L0, Lk, L1, Lk-1, L2, Lk-2, ... sırasına göre yeniden düzenle: önce ilk düğüm, sonra son düğüm, ardından ikinci düğüm, sonra sondan ikinci düğüm ve bu şekilde devam et. Değerleri bu yeni sırayla döndür.
Fonksiyon
- nextinteger-array
- her düğümün bağlantı verdiği düğümün indeksi veya son düğüm için -1
- valuesinteger-array
- her bir düğümün tuttuğu değer
- Döndürürinteger-array
- yeniden sıralanmış listedeki sıraya göre değerler
Kısıtlar
1 ≤ n ≤ 4000; buradan,nextvevaluesuzunluğudur.-1000 ≤ values[i] ≤ 1000- Her bir
next[i],-1ya da0ilen-1arasında bir düğüm indeksidir. - Başlangıç düğümü
0olan liste, her düğümü tam olarak bir kez ziyaret eder ve ardından-1değerine ulaşır. Döngü yoktur.
Örnekler
- Girdi
- next = [3, 4, -1, 1, 2]values = [1, 3, 5, 2, 4]
- Çıktı
- [1, 5, 2, 4, 3]
- Açıklama
0düğümünden bağlantıları takip ettiğimizde liste1, 2, 3, 4, 5şeklinde okunur. İlk, son, ikinci ve sondan ikinci değerler1, 5, 2, 4olur ve orta değer olan3en sona gelir.
- Girdi
- next = [2, 3, 1, -1]values = [10, 30, 20, 40]
- Çıktı
- [10, 40, 20, 30]
- Açıklama
- Liste,
0, 2, 1, 3düğümlerini ziyaret eder ve10, 20, 30, 40değerlerini okur. İlk ve son değerler10, 40olur; ardından içteki çift20, 30değerlerini verir.
- Girdi
- next = [-1]values = [7]
- Çıktı
- [7]
- Açıklama
- Tek düğümlü bir listede taşınacak hiçbir şey yoktur, bu yüzden yanıt
[7]olur.
Ek soru
Bağlantıların kendilerini O(1) ek bellek kullanarak yeniden sıralayabilir misin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
1, 2, 3, 4, 5, 6için hedef sırayı yazın. Listenin ön yarısından hangi düğümler gelir ve arka yarıdaki düğümler hangi sırayla görünür?Arka yarı ters sırada görünür:
6, 5, 4. Arka yarı ters çevrilseydi, cevap her seferinde iki listeden bir düğüm alınarak birleştirilmiş iki liste olurdu.Bir bağlantı ilerleyen yavaş bir işaretçi ve iki bağlantı ilerleyen hızlı bir işaretçiyle ortayı bulun. Listeyi ortadan sonra kesin, ikinci kısmı bağlantılarını tersine çevirerek ters çevirin, ardından iki kısmı düğüm düğüm iç içe geçirin.
Çözüm
Yeni sıralama ön ve arka taraf arasında dönüşümlüdür, ancak tek yönlü bağlı liste yalnızca ileri doğru ilerler. İşi üç standart liste işlemi olarak böl: yavaş ve hızlı işaretçilerle ortayı bul, arka yarıyı ters çevir ve iki yarıyı her seferinde bir düğüm alarak iç içe geçir.
Kuyruğu her seferinde bir düğüm ileri taşı
Sezgi
Burada bir işaretçi bir düğüm indeksidir ve ilerlemek için node = next[node] kullanılır. İlk düğümden sonra son düğüm gelir; bu nedenle son düğümü çıkarıp geçerli düğümden sonra ekleyin, ardından iki düğüm ileride yineleyin. 1, 2, 3, 4, 5 için sonuç 1, 5, 2, 3, 4, ardından 1, 5, 2, 4, 3 olur. Geçerli düğümden sonra ikiden az düğüm kaldığında durun.
Sondan bir önceki düğümü bulmak, her turda sona kadar ilerlemeyi gerektirir. Yürüyüşler her turda iki düğüm kısalır; toplamda yaklaşık n²/4 adım eder: 4000 düğüm için dört milyon.
Algoritma
cur = 0olarak ayarla.cur'den sonra en az iki düğüm olduğu sürece,next[next[before]] == -1olana kadarbefore'ucur'den başlayarak ilerlet; böylecetail = next[before]son düğüm olur.next[before] = -1ile bağlantısını kes, ardından ekle:next[tail] = next[cur]venext[cur] = tail.cur'unext[tail]'e taşı ve tekrarla.0düğümünden başlayarak ilerle ve değerleri topla.
def reorderList(next, values):
cur = 0
# While at least two nodes follow cur, move the last node right after cur.
while next[cur] != -1 and next[next[cur]] != -1:
before = cur
while next[next[before]] != -1: # find the node before the tail
before = next[before]
tail = next[before]
next[before] = -1
next[tail] = next[cur]
next[cur] = tail
cur = next[tail]
result = []
node = 0
while node != -1:
result.append(values[node])
node = next[node]
return resultDeğerleri kopyalayın ve iki uçtan da okuyun
Sezgi
Bir dizi son elemanına tek adımda ulaşır. Değerleri liste sırasına göre kopyala; ilk örnekteki [1, 2, 3, 4, 5] gibi. Ardından önden lo, arkadan hi ile oku: lo'yu al, hi'yi al ve lo < hi iken ikisini de ortaya doğru ilerlet. Böylece 1, 5, 2, 4 elde edilir; uzunluk tek olduğunda ikisi ortadaki 3'te buluşur ve bu değer en sona gider.
Bu, O(n) zaman ve O(n) ek bellek gerektirir; bağlantılar hiç değişmez.
Algoritma
0düğümünden başlayarak ilerleyin ve her değeriinOrder'a ekleyin.lo = 0olarak ayarlayın vehideğerini son indeks olarak belirleyin.lo < hiolduğu süreceinOrder[lo]veinOrder[hi]değerlerini ekleyin, ardındanlodeğerini artırıphideğerini azaltın.lo == hiise ortadaki değeri ekleyin.
def reorderList(next, values):
# Write the values out in list order.
in_order = []
node = 0
while node != -1:
in_order.append(values[node])
node = next[node]
# Take from the front and the back in turn.
result = []
lo, hi = 0, len(in_order) - 1
while lo < hi:
result.append(in_order[lo])
result.append(in_order[hi])
lo += 1
hi -= 1
if lo == hi: # odd length: the middle value comes last
result.append(in_order[lo])
return resultOrtayı bul, arka yarıyı tersine çevir, iç içe geçir
Sezgi
1, 2, 3, 4, 5, 6 için cevap 1, 6, 2, 5, 3, 4: baştaki yarı 1, 2, 3 sırasıyla, sondaki yarı 4, 5, 6 ise tersten okunarak sırayla birleştirilir. Bu yüzden listeyi ortadan kes, sondaki yarıyı ters çevir ve iç içe geçir.
slow bir bağlantı ilerlerken fast iki bağlantı ilerler; bu nedenle slow, beş ya da altı düğüm olduğunda baştaki yarının son düğümünde, yani 3 üzerinde durur. Bu düğümden sonra kesmek, uzunluk tek olduğunda baştaki yarıya fazladan düğüm verir ve bu düğüm cevabın sonunda yer alır. Sondaki yarı tükenene kadar iç içe geçirme işlemi sırayla her yarıdan bir düğüm alır.
Her düğüme sabit sayıda kez erişilir ve bellekte birkaç indeks tutulur. R, ilk değişiklikte bağlantı vektörünün bir kopyasını oluşturur; bu nedenle R'de bellek kullanımı O(n) olur.
Algoritma
next[fast]venext[next[fast]],-1olmadığı süreceslow'u bir düğüm,fast'i iki düğüm ilerlet.second = next[slow]olarak ayarla, ardındannext[slow] = -1yap.second'dan başlayan listeyi tersine çevir; yeni başıprevolur.- İç içe geçir:
second,-1olmadığı sürecefirst'isecond'a,second'ı dafirst'in eskinext[first]değerine bağla, ardından her ikisini de ilerlet. 0düğümünden ilerle ve değerleri topla.
def reorderList(next, values):
# 1. Find the middle: slow stops on the last node of the first half.
slow = fast = 0
while next[fast] != -1 and next[next[fast]] != -1:
slow = next[slow]
fast = next[next[fast]]
second = next[slow]
next[slow] = -1 # cut the list in two
# 2. Reverse the second half.
prev = -1
while second != -1:
after = next[second]
next[second] = prev
prev = second
second = after
# 3. Weave: one node from the front half, one from the reversed back half.
first, second = 0, prev
while second != -1:
first_after, second_after = next[first], next[second]
next[first] = second
next[second] = first_after
first, second = first_after, second_after
result = []
node = 0
while node != -1:
result.append(values[node])
node = next[node]
return result
Tuzaklar ve uç durumlar
- Listeyi ortasından kesmemek.
next[slow] = -1olmadan ön yarı hâlâ arka yarıya işaret eder ve iç içe geçirme işleminden sonra liste kendi üzerine döngü yapar. - Bağlantıyı kaydetmeden önce üzerine yazmak. Ters çevirme ve iç içe geçirme sırasında, listenin geri kalanını kaybetmemek için önce
next[node]değerini bir değişkene alın. - Ön yarı bitene kadar iç içe geçirme işlemini sürdürmek. Uzunluk tek olduğunda bu döngü,
seconddeğeri-1iken bir kez daha çalışır venext[-1]değerini okur. - Dizi sırasını liste sırası olarak okumak. İlk örnekte
valuesdeğeri[1, 3, 5, 2, 4]olsa da liste1, 2, 3, 4, 5şeklindedir. - Lua ve R'de diziler 1'den başlar. Düğüm indekslerini 0 tabanlı tutun ve
next[node + 1]değerini okuyun.
Sıkça sorulan sorular3
Listenin ikinci yarısını neden tersine çeviriyoruz?
Cevap, ikinci yarıyı son düğümünden ilk düğümüne doğru okur; tek yönlü bağlı liste ise yalnızca ileri doğru ilerler. İkinci yarıyı O(n) zamanda bir kez ters çevirmek, birleştirmenin her iki yarıda da ileri doğru ilerlemesini sağlar.
Reorder List'in zaman karmaşıklığı nedir?
Yerinde yöntem O(n) zamanda ve O(1) ek bellekle çalışır: Ortayı bulma, ters çevirme ve iç içe geçirme işlemlerinin her biri her düğümü sabit sayıda ziyaret eder. Değerleri bir diziye kopyalamak da O(n) zaman alır, ancak O(n) bellek gerektirir; kuyruğu her seferinde bir düğüm ilerletmek ise O(n²) sürer.
Liste çift sayıda düğüm içerdiğinde orta nokta neresidir?
Yavaş işaretçiyi ön yarının son düğümünde durdurun. Altı düğüm olduğunda yarılar üç ve üç; beş düğüm olduğunda ise üç ve ikidir. Fazladan düğüm yanıtı bitirir; sıralamada orta değerin bulunduğu yer burasıdır.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def reorderList(next, values):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argümanlar
next = [3, 4, -1, 1, 2] values = [1, 3, 5, 2, 4]
Beklenen Çıktı
[1, 5, 2, 4, 3]