Reverse Linked List

Q: Bağlı bir liste yerinde nasıl ters çevrilir?

Listeyi iki işaretçiyle dolaş: prev başlangıçta hiçbir şeyi göstermesin, node ise baş düğümü göstersin. Her düğümde, sonraki düğümünü kaydet, bağlantısını prev düğümünü gösterecek şekilde ayarla, ardından prev ve node işaretçilerini bir adım ilerlet. node sona geldiğinde, ters çevrilmiş listenin başı prev olur.

Q: Bağlı bir listeyi tersine çevirmenin zaman ve uzay karmaşıklığı nedir?

Yinelemeli sürüm her düğümü bir kez ziyaret eder, O(n) zaman alır ve üç işaretçi tutar; ek alan kullanımı O(1) ’dir. Sıralamayı önce bir diziye kopyalamak da O(n) zaman alır ancak O(n) ek alan gerektirir. Özyinelemeli bir sürüm, çağrı yığını için O(n) alan kullanır.

KolayBağlı liste

+10

next dizisinde saklanan tek yönlü bağlı bir listeniz var: i düğümü 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 edin.

Her bağlantıyı tersine çevirerek listeyi tersine çevirin; böylece eski son düğüm baş düğüm olur ve 0 düğümü, -1'e bağlanarak son düğüm olur. Girdiyle aynı uzunluğa sahip olan güncellenmiş next dizisini döndürün.

Fonksiyon

reverseList(next: integer-array) → integer-array

nextinteger-array: düğümün bağlandığı her bir düğümün indeksi veya son düğüm için -1
Döndürürinteger-array: ters çevrilmiş listenin sonraki dizisi

Kısıtlar

1 ≤ next.length ≤ 5000
Her next[i], -1 ya da 0 ile next.length-1 arasında bir düğüm indeksidir.
0 düğümünden başlayarak liste her düğümü tam olarak bir kez ziyaret eder ve ardından -1'e ulaşır. Döngü yoktur.

Örnekler

Girdi: next = [1, 2, 3, -1]
Çıktı: [-1, 0, 1, 2]
Açıklama: Liste 0 → 1 → 2 → 3 şeklindedir. Ters çevrildiğinde 3 → 2 → 1 → 0 olur; bu nedenle 3 düğümü 2'ye, 2 düğümü 1'e, 1 düğümü 0'a ve 0 düğümü -1'e bağlanır.

Girdi: next = [2, -1, 3, 1]
Çıktı: [-1, 3, 0, 2]
Açıklama: Liste 0 → 2 → 3 → 1 şeklindedir; tersine çevrildiğinde 1 → 3 → 2 → 0 olur. Her yeni bağlantıyı düğümünün indeksine yazmak [-1, 3, 0, 2] sonucunu verir. Dizinin kendisini tersine çevirmek ise [1, 3, -1, 2] sonucunu verir; bu aynı şey değildir.

Girdi: next = [-1]
Çıktı: [-1]
Açıklama: Bir düğüm kendi tersidir. Baş ve kuyruk olarak kalır ve yine -1 değerine bağlanır.

Gönderirken +11 gizli test

Ek soru

Listenin yalnızca left konumu ile right konumu arasındaki bölümünü tersine çevirip, öncesindeki ve sonrasındaki düğümleri oldukları yerde bırakabilir misin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Bir listeyi tersine çevirmek hiçbir düğümü taşımaz; her bağlantının yönünü değiştirir. Sorun şu ki bir düğümün bağlantısı, listenin geri kalanına ulaşmanın tek yoludur; bu yüzden bağlantının üzerine yazdığınız anda ondan sonraki her şey kaybolur. Sıralamayı önce not ederek bu sorunu önleyebilir ya da her bağlantının yönünü değiştirmeden önce ileri giden yolu kaydeden üç işaretçiyle listeyi bir kez dolaşabilirsiniz.

Sıralamayı not et, ardından yeniden bağla

Sezgi

Bu problemde işaretçi bir düğüm indeksidir ve ileri gitmek node = next[node] işlemidir. -1 değerine ulaşana kadar 0 düğümünden ilerleyin ve geçtiğiniz her düğümü not edin. İkinci örnekte elde edilen sıra [0, 2, 3, 1] olur.

Ters çevrilmiş listede her düğüm, bu sırada kendisinden önce gelen düğüme bağlanır: 1, 3'e; 3, 2'ye; 2 ise 0'a bağlanır. Sıradaki ilk düğüm olan eski baş düğümün öncesinde hiçbir düğüm yoktur, bu yüzden -1'e bağlanır. Yeni bir diziyi bu bağlantılarla doldurun ve diziyi döndürün.

Her bağlantı yeni bir diziye yazıldığı için, hâlâ ihtiyaç duyduğunuz hiçbir şeyin üzerine yazılmaz; bu da bu sürümde hata yapmayı zorlaştırır. Bu işlem O(n) zaman ve sıralama ile yeni dizi için O(n) ek bellek alır.

Algoritma

0 düğümünden -1 düğümüne kadar ilerleyin ve her düğümü order dizisine ekleyin.
Aynı uzunlukta yeni bir dizi oluşturun.
order[0] girişini -1 olarak ayarlayın.
Her k ≥ 1 için order[k] girişini order[k-1] olarak ayarlayın.
Yeni diziyi döndürün.

def reverseList(next):
    order = []
    node = 0
    while node != -1:
        order.append(node)
        node = next[node]
    reversed_next = [0] * len(next)
    reversed_next[order[0]] = -1  # the old head ends the new list
    for k in range(1, len(order)):
        reversed_next[order[k]] = order[k - 1]
    return reversed_next

Bağlantıların yönünü tek geçişte tersine çevir

Sezgi

Her bağlantıyı düğümüne ulaştığın anda, geldiğin düğümü hatırlıyorsan tersine çevirebilirsin. Arkandaki düğüm olan prev değişkenini, eski baş düğüm son düğüm olacağı için başlangıçta -1 olarak ayarla. node düğümündeyken next[node] bağlantısı ileriye doğru işaret eder; geriye doğru işaret etmesi için bunu prev olarak ayarla.

Bu yazma işlemi ileriye gitmenin tek yolunu yok eder; bu yüzden önce üçüncü bir değişkende sakla: after = next[node]. Ardından bağlantıyı tersine çevir ve her iki işaretçiyi de bir adım ilerlet: prev = node, node = after. Her an, arkandaki düğümler başında prev olan ters çevrilmiş bir liste oluşturur; önündeki düğümler ise node ile başlayan, henüz değiştirilmemiş kısımdır. node -1 değerine ulaştığında tüm bağlantılar tersine çevrilmiş olur ve prev yeni baş düğümü gösterir.

İkinci örnekte işaretçiler 0, 2, 3, 1 düğümlerinde ilerler ve next[0] = -1, next[2] = 0, next[3] = 2 ve next[1] = 3 yazar. Her düğüm bir kez ziyaret edilir; zaman karmaşıklığı O(n) olur ve kullanılan tek bellek üç tam sayıdır: O(1).

Algoritma

prev = -1 ve node = 0 olarak ayarla.
node, -1 olmadığı sürece after = next[node] değerini kaydet.
next[node] = prev olarak ayarla.
İlerle: prev = node, ardından node = after.
next değerini döndür.

def reverseList(next):
    prev = -1  # the node behind the current one; the old head will point to -1
    node = 0
    while node != -1:
        after = next[node]  # save the rest of the list before cutting the link
        next[node] = prev
        prev = node
        node = after
    return next

Tuzaklar ve uç durumlar

Buradaki hataların neredeyse tamamı, üç atamanın sırasıyla veya listenin iki ucuyla ilgilidir.

next[node] değerini kaydetmeden üzerine yazmak. next[node] = prev işleminden sonra eski ileri bağlantı kaybolur ve ilerleme, sonraki düğüme devam etmek yerine geriye sıçrar.
prev değerini -1 dışında bir değerle başlatmak. Eski baş, yeni listenin sonu olmalıdır. 0 ile başlatmak, 0 düğümünün kendisine bağlanmasına neden olur.
Bağlantılar yerine diziyi ters çevirmek. Düğümler liste sırasına göre saklanmaz ve yanıtta her düğüm kendi indeksinde kalır; yalnızca değerler değişir. [2, -1, 3, 1] dizisini ters çevirmek, [-1, 3, 0, 2] yerine [1, 3, -1, 2] sonucunu verir.
next[node] != -1 koşuluyla döngü kurup bir düğüm erken durmak. Son düğümün bağlantısı da ters çevrilmelidir; bu yüzden node != -1 koşuluyla döngüye devam edin.
Uzun bir listeyi özyinelemeyle ters çevirmek. 5000 düğümlü bir liste, Python'ın 1000 olan sınırını aşarak 5000 iç içe çağrı gerektirir.
Dizilerin 1'den başladığı Lua ve R dillerinde ofseti unutmak. Düğüm indekslerini 0 tabanlı tutun ve next[node + 1] değerini okuyun. Ruby ve R, next sözcüğünü ayırdığından, bu dillerdeki başlangıç kodlarında parametreye next_ adı verilir.

Sıkça sorulan sorular4

Bağlı bir liste yerinde nasıl ters çevrilir?

Listeyi iki işaretçiyle dolaş: prev başlangıçta hiçbir şeyi göstermesin, node ise baş düğümü göstersin. Her düğümde, sonraki düğümünü kaydet, bağlantısını prev düğümünü gösterecek şekilde ayarla, ardından prev ve node işaretçilerini bir adım ilerlet. node sona geldiğinde, ters çevrilmiş listenin başı prev olur.

Bağlı bir listeyi tersine çevirmenin zaman ve uzay karmaşıklığı nedir?

Yinelemeli sürüm her düğümü bir kez ziyaret eder, O(n) zaman alır ve üç işaretçi tutar; ek alan kullanımı O(1)’dir. Sıralamayı önce bir diziye kopyalamak da O(n) zaman alır ancak O(n) ek alan gerektirir. Özyinelemeli bir sürüm, çağrı yığını için O(n) alan kullanır.

Bağlı bir listeyi özyinelemeli olarak tersine çevirebilir misin?

Evet. Baş düğümden sonraki her şeyi tersine çevir, ardından baş düğümün eski sonraki düğümünü baş düğüme geri bağla ve baş düğümün bağlantısını boş olarak ayarla. Okuması kolaydır, ancak her düğüm için iç içe bir çağrı yapar; bu nedenle uzun bir liste çağrı yığınını taşırabilir. Python varsayılan olarak 1000 çağrıda durur; 5000 düğümlü bir liste bu sınırı aşar.

Bağlı bir listeyi tersine çevirmek neden üç işaretçi gerektirir?

Bir düğümün bağlantısını tersine çevirmek için düğümün kendisine ve ondan önceki düğüme ihtiyacın var; yani iki işaretçiye. Üçüncü işaretçi, bağlantıyı tersine çevirmek listenin geri kalanına olan tek referansı sileceği için düğümden sonraki düğümü tutar. Bu olmadan ilerlemeye devam edemezsin.

Python

def reverseList(next):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

next = [1, 2, 3, -1]

Beklenen

[-1, 0, 1, 2]