Palindrome Linked List

Q: Palindrom bağlı liste kontrolünün zaman karmaşıklığı nedir?

L düğümden oluşan bir liste için her yaklaşımın zaman karmaşıklığı O(L) olur, çünkü her değerin karşılaştırılması gerekir. Değerleri bir diziye veya yığına kopyalamak O(L) ek bellek kullanır; ikinci yarıyı yerinde tersine çevirmek ise O(1) kullanır.

Q: Hızlı ve yavaş işaretçiler bağlı bir listenin ortasını nasıl bulur?

İkisi de baştan başlar ve hızlı işaretçi, yavaş işaretçinin her adımına karşılık iki adım atar. Hızlı işaretçi sona ulaştığında listenin tamamını, yavaş işaretçi ise yarısını katetmiş olur.

Q: Listenin yarısını tersine çevirmek girdiyi bozar mı?

Evet, ikinci yarının bağlantılarını değiştirir ve çoğu dilde bu dizi çağırana aittir. Listeye hâlâ ihtiyaç varsa, erken dönmeden karşılaştırmayı tamamlayın, ardından o yarıyı tekrar ters çevirin. Orta düğüm hâlâ o yarının ilk düğümüne bağlıdır; böylece liste, O(1) ek bellekle yeniden bütün hâle gelir.

KolayBağlı liste Hızlı ve yavaş işaretçiler İki işaretçi

+10

Aynı uzunluktaki 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 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.

Değerler baştan sona ve sondan başa okunduğunda aynıysa true, aksi takdirde false döndürün.

Fonksiyon

isPalindrome(next: integer-array, values: integer-array) → boolean

nextinteger-array: her düğümün bağlantı verdiği düğümün indeksi veya son düğüm için -1
valuesinteger-array: her düğümün tuttuğu değer
Döndürürboolean: liste her iki yönde de aynı okunuyorsa true

Kısıtlar

1 ≤ L ≤ 5000; burada L, next ve values uzunluğudur.
-100 ≤ values[i] ≤ 100
Her next[i], -1 ya da 0 ile L-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 = [4, 3, -1, 2, 1]values = [3, 4, 3, 1, 1]
Çıktı: true
Açıklama: Bağlantılar 0, 4, 1, 3, 2 düğümlerini ziyaret eder; bu nedenle liste 3, 1, 4, 1, 3 şeklindedir. İki 3 eşleşir, iki 1 eşleşir ve ortadaki 4 için kontrol edilecek bir eş yoktur.

Girdi: next = [2, -1, 3, 1]values = [4, 4, 9, 9]
Çıktı: true
Açıklama: Liste, 0, 2, 3, 1 düğümlerini ziyaret eder ve her iki yönde de aynı olan 4, 9, 9, 4 değerlerini okur.

Girdi: next = [2, -1, 1]values = [1, 2, 1]
Çıktı: false
Açıklama: values dizisi [1, 2, 1], ancak liste 0, 2, 1 düğümlerini ziyaret eder ve 1, 1, 2 değerlerini okur. Tersten bakıldığında bu 2, 1, 1 olur, dolayısıyla cevap false.

Ek soru

Bunu O(L) zamanda ve O(1) ek bellekle yapabilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Palindrom kontrolü, her değeri diğer uçtaki karşılığıyla eşleştirir. Tek yönlü bağlı liste yalnızca ileri doğru ilerler; bu yüzden zor olan, arka yarıyı tersten okumaktır. Bir dizi kopyası bunu O(L) bellekle yapar; burada L, düğüm sayısıdır. İkinci yarının bağlantılarını tersine çevirmek ise bunu O(1) ile yapar.

Değerleri bir diziye kopyala

Sezgi

Buradaki bir işaretçi düğüm indeksidir ve ilerlemek için node = next[node] kullanılır. Listeyi bir kez dolaşıp her değeri, iki uçtan da okuyabileceğin bir diziye kopyala. İlk ve son değerleri karşılaştır, her iki indeksi de ortaya doğru ilerlet ve herhangi bir uyuşmazlıkta false döndür. Uzunluk tek olduğunda ortadaki değerin eşi kendisidir.

Her değer okunmak zorunda olduğundan, O(L) süre mümkün olan en iyi süredir. Bunun bedeli L ek tamsayıdır.

Algoritma

0 düğümünden -1 düğümüne kadar ilerleyin ve her values[node] değerini bir diziye ekleyin.
i = 0 olarak ayarlayın ve j değerini son indeks olarak belirleyin.
i < j iken, iki değer farklıysa false döndürün; aksi takdirde i değerini artırın ve j değerini azaltın.
true döndürün.

def isPalindrome(next, values):
    # Write the values out in list order.
    seq = []
    node = 0
    while node != -1:
        seq.append(values[node])
        node = next[node]
    # Compare from both ends toward the middle.
    i = 0
    j = len(seq) - 1
    while i < j:
        if seq[i] != seq[j]:
            return False
        i += 1
        j -= 1
    return True

İkinci yarıyı yerinde tersine çevir

Sezgi

Arka yarıyı kopyalamak yerine bağlantılarını tersine çevirin: eski son düğümden başlayarak ilerlemek sizi ortaya götürür. Ortayı bulmak için fast, slow her bir bağlantı ilerlediğinde iki bağlantı ilerlesin; bunu fast'in önünde iki bağlantı olduğu sürece yapın. slow, ilk yarının son düğümünde, L tek olduğunda ise orta düğümde durur. İlk örnekte slow 0 → 4 → 1 ilerlerken fast 0 → 1 → 2 ilerler; böylece slow 4'te durur.

slow'dan sonraki düğümleri tersine çevirin, ardından baş düğümden başlayan left ile tersine çevrilmiş yarıdan başlayan right'ı birlikte ilerletin: önce 3 ile 3, sonra 1 ile 1. Tersine çevrilmiş yarı hiçbir zaman ilk yarıdan uzun olmaz; bu nedenle right sona erdiğinde durmak, tam olarak önemli olan çiftleri karşılaştırır. Her aşama en fazla L düğüm boyunca ilerler ve birkaç tam sayı saklar. R'de next_'i değiştirmek vektörü bir kez kopyalar; bu nedenle R, O(L) bellek kullanır.

Algoritma

slow = fast = 0 olarak ayarla. next[fast] ve next[next[fast]] değerlerinin ikisi de -1 olmadığı sürece slow'u bir bağlantı, fast'i iki bağlantı ilerlet.
next[slow] konumunda başlayan listeyi tersine çevir: her düğüm için bağlantısını kaydet, onu prev'e yönlendir, ardından prev'i ve düğümü ilerlet.
left = 0 ve ters çevrilmiş yarının başı olan right = prev olarak ayarla.
right != -1 olduğu sürece, bir uyuşmazlık varsa false döndür; aksi takdirde her iki işaretçiyi de bir bağlantı ilerlet.
true döndür.

def isPalindrome(next, values):
    # Find the middle: fast moves two links for every one link slow moves.
    slow = 0
    fast = 0
    while next[fast] != -1 and next[next[fast]] != -1:
        slow = next[slow]
        fast = next[next[fast]]
    # slow is the last node of the first half (the middle node when the length is odd).
    # Reverse the links of the second half.
    prev = -1
    node = next[slow]
    while node != -1:
        after = next[node]
        next[node] = prev
        prev = node
        node = after
    # prev is the old last node, now the head of the reversed half.
    left = 0
    right = prev
    while right != -1:
        if values[left] != values[right]:
            return False
        left = next[left]
        right = next[right]
    return True

Tuzaklar ve uç durumlar

Liste yerine dizileri kontrol etmek. Üçüncü örnekte values, [1, 2, 1] değerindedir, ancak liste 1, 1, 2 şeklindedir.
Yalnızca next[fast] != -1 koşulunu test etmek. fast daha sonra -1 değerine atlayıp next[-1] değerini okuyabilir; bu, çoğu dilde aralık dışıdır ve Python ile Ruby'de sessizce son öğeyi verir.
right yerine left bitene kadar karşılaştırmak. Orta düğüm hâlâ eski ikinci yarıya bağlıdır, bu yüzden baştan yapılan yürüyüş daha uzundur.
Tersine çevirme sırasında kaydetmeden önce next[node] değerinin üzerine yazmak; bu, listenin geri kalanını kaybettirir.
Dizilerin 1'den başladığı Lua ve R'de, 0 tabanlı bir düğüm kimliği için next[node] değerini okumak. next[node + 1] değerini oku.

Sıkça sorulan sorular3

Palindrom bağlı liste kontrolünün zaman karmaşıklığı nedir?

L düğümden oluşan bir liste için her yaklaşımın zaman karmaşıklığı O(L) olur, çünkü her değerin karşılaştırılması gerekir. Değerleri bir diziye veya yığına kopyalamak O(L) ek bellek kullanır; ikinci yarıyı yerinde tersine çevirmek ise O(1) kullanır.

Hızlı ve yavaş işaretçiler bağlı bir listenin ortasını nasıl bulur?

İkisi de baştan başlar ve hızlı işaretçi, yavaş işaretçinin her adımına karşılık iki adım atar. Hızlı işaretçi sona ulaştığında listenin tamamını, yavaş işaretçi ise yarısını katetmiş olur.

Listenin yarısını tersine çevirmek girdiyi bozar mı?

Evet, ikinci yarının bağlantılarını değiştirir ve çoğu dilde bu dizi çağırana aittir. Listeye hâlâ ihtiyaç varsa, erken dönmeden karşılaştırmayı tamamlayın, ardından o yarıyı tekrar ters çevirin. Orta düğüm hâlâ o yarının ilk düğümüne bağlıdır; böylece liste, O(1) ek bellekle yeniden bütün hâle gelir.

def isPalindrome(next, values):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argümanlar

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

Beklenen Çıktı

true