Palindrome Linked List

Q: Berapa kompleksitas waktu untuk pemeriksaan linked list palindrom?

Setiap pendekatan memiliki kompleksitas O(L) untuk list yang terdiri dari L node, karena setiap nilai harus dibandingkan. Menyalin nilai ke dalam array atau ke stack menggunakan memori tambahan sebesar O(L) ; membalik paruh kedua secara langsung menggunakan O(1) .

Q: Bagaimana pointer cepat dan lambat menemukan bagian tengah linked list?

Keduanya mulai dari kepala, dan pointer cepat melangkah dua kali untuk setiap satu langkah pointer lambat. Saat pointer cepat mencapai akhir, pointer itu telah menempuh seluruh list, sedangkan pointer lambat telah menempuh setengahnya.

Q: Apakah membalik setengah dari list akan merusak input?

Ya, ini mengubah tautan pada bagian kedua, dan dalam sebagian besar bahasa, array itu milik pemanggil. Jika list masih diperlukan, selesaikan perbandingan tanpa langsung mengembalikan hasil, lalu balikkan bagian itu lagi. Simpul tengah tetap tertaut ke simpul pertama pada bagian tersebut, sehingga list kembali utuh dengan memori tambahan O(1) .

MudahLinked list Pointer cepat dan lambat Two pointers

+10

Kamu mendapatkan singly linked list yang disimpan dalam dua array dengan panjang yang sama. Node i menyimpan nilai values[i] dan terhubung ke node next[i], -1 menandai akhir list, dan head adalah node 0. Node-node tersebut tidak disimpan sesuai urutan list, jadi ikuti tautannya.

Kembalikan true jika nilai yang dibaca dari head sampai akhir sama dengan nilai yang dibaca dari akhir kembali ke head, dan false jika tidak.

Fungsi

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

nextinteger-array: indeks node yang ditautkan oleh setiap node, atau -1 untuk node terakhir
valuesinteger-array: nilai yang disimpan oleh setiap node
Mengembalikanboolean: true jika list terbaca sama dari kedua arah

Batasan

1 ≤ L ≤ 5000, dengan L adalah panjang next dan values.
-100 ≤ values[i] ≤ 100
Setiap next[i] adalah -1 atau indeks simpul dari 0 hingga L-1.
Mulai dari node 0, list mengunjungi setiap node tepat satu kali lalu mencapai -1. Tidak ada siklus.

Contoh

Input: next = [4, 3, -1, 2, 1]values = [3, 4, 3, 1, 1]
Output: true
Penjelasan: Tautan mengunjungi node 0, 4, 1, 3, 2, jadi list-nya terbaca 3, 1, 4, 1, 3. Kedua angka 3 cocok, kedua angka 1 cocok, dan 4 di tengah tidak memiliki pasangan untuk diperiksa.

Input: next = [2, -1, 3, 1]values = [4, 4, 9, 9]
Output: true
Penjelasan: list mengunjungi node 0, 2, 3, 1 dan membaca 4, 9, 9, 4, sama di kedua arah.

Input: next = [2, -1, 1]values = [1, 2, 1]
Output: false
Penjelasan: array values adalah [1, 2, 1], tetapi list mengunjungi node 0, 2, 1 dan membaca 1, 1, 2. Jika dibalik, hasilnya 2, 1, 1, jadi jawabannya false.

Pertanyaan lanjutan

Bisakah kamu melakukannya dalam waktu O(L) dengan memori tambahan O(1)?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Pemeriksaan palindrom memasangkan setiap nilai dengan nilai cerminnya dari ujung yang lain. Singly linked list hanya bergerak ke depan, jadi bagian tersulitnya adalah membaca separuh bagian belakang secara terbalik. Salinan array melakukannya dengan memori O(L), dengan L sebagai jumlah node; membalik tautan pada separuh bagian kedua melakukannya dengan O(1).

Salin nilai-nilainya ke dalam array

Intuisi

Pointer di sini adalah indeks node, dan untuk bergerak maju gunakan node = next[node]. Telusuri list sekali dan salin setiap nilai ke dalam array, yang bisa kamu baca dari kedua ujungnya. Bandingkan nilai pertama dan terakhir, gerakkan kedua indeks ke arah tengah, lalu kembalikan false jika ada nilai yang tidak cocok. Jika panjangnya ganjil, nilai tengah menjadi pasangannya sendiri.

Setiap nilai harus dibaca, jadi waktu O(L) adalah yang paling optimal. Biayanya adalah L integer tambahan.

Algoritma

Berjalanlah dari node 0 hingga -1 dan tambahkan setiap values[node] ke array.
Tetapkan i = 0 dan j ke indeks terakhir.
Selama i < j, kembalikan false jika kedua nilai berbeda, jika tidak, naikkan i dan turunkan j.
Kembalikan true.

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

Balikkan bagian kedua di tempatnya

Intuisi

Balikkan tautan pada separuh bagian belakang, bukan menyalinnya: berjalan dari simpul terakhir yang lama akan mengarah ke tengah. Untuk menemukan bagian tengah, gerakkan fast dua tautan untuk setiap satu tautan yang digerakkan slow, selama fast memiliki dua tautan di depannya. slow berhenti di simpul terakhir separuh bagian pertama, yaitu simpul tengah saat L ganjil. Pada contoh pertama, slow bergerak 0 → 4 → 1, sedangkan fast bergerak 0 → 1 → 2, jadi slow berhenti di 4.

Balikkan simpul-simpul setelah slow, lalu gerakkan left dari kepala dan right dari separuh bagian yang dibalik secara bersamaan: 3 dengan 3, lalu 1 dengan 1. Separuh bagian yang dibalik tidak pernah lebih panjang daripada separuh bagian pertama, jadi berhenti saat right berakhir akan membandingkan tepat pasangan yang perlu dibandingkan. Setiap tahap menelusuri paling banyak L simpul dan menyimpan beberapa bilangan bulat. Di R, mengubah next_ akan menyalin vektor satu kali, jadi R menggunakan memori O(L).

Algoritma

Tetapkan slow = fast = 0. Selama next[fast] dan next[next[fast]] keduanya bukan -1, gerakkan slow satu tautan dan fast dua tautan.
Balikkan list yang dimulai dari next[slow]: untuk setiap node, simpan tautannya, arahkan ke prev, lalu gerakkan prev dan node tersebut ke depan.
Tetapkan left = 0 dan right = prev, yaitu kepala dari bagian yang dibalik.
Selama right != -1, kembalikan false jika ada ketidakcocokan, jika tidak, gerakkan kedua pointer satu tautan.
Kembalikan true.

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

Jebakan dan kasus tepi

Memeriksa array, bukan list. Pada contoh ketiga, values adalah [1, 2, 1], tetapi list berisi 1, 1, 2.
Hanya menguji next[fast] != -1. fast kemudian dapat melompat ke -1 dan membaca next[-1], yang berada di luar rentang dalam sebagian besar bahasa dan secara diam-diam mengakses entri terakhir di Python dan Ruby.
Membandingkan sampai left habis, bukan right. Node tengah masih terhubung ke paruh kedua yang lama, sehingga penelusuran dari head menjadi lebih panjang.
Menimpa next[node] selama pembalikan sebelum menyimpannya, sehingga bagian list lainnya hilang.
Di Lua dan R, yang array-nya dimulai dari 1, membaca next[node] untuk id node berbasis 0. Baca next[node + 1].

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu untuk pemeriksaan linked list palindrom?

Setiap pendekatan memiliki kompleksitas O(L) untuk list yang terdiri dari L node, karena setiap nilai harus dibandingkan. Menyalin nilai ke dalam array atau ke stack menggunakan memori tambahan sebesar O(L); membalik paruh kedua secara langsung menggunakan O(1).

Bagaimana pointer cepat dan lambat menemukan bagian tengah linked list?

Keduanya mulai dari kepala, dan pointer cepat melangkah dua kali untuk setiap satu langkah pointer lambat. Saat pointer cepat mencapai akhir, pointer itu telah menempuh seluruh list, sedangkan pointer lambat telah menempuh setengahnya.

Apakah membalik setengah dari list akan merusak input?

Ya, ini mengubah tautan pada bagian kedua, dan dalam sebagian besar bahasa, array itu milik pemanggil. Jika list masih diperlukan, selesaikan perbandingan tanpa langsung mengembalikan hasil, lalu balikkan bagian itu lagi. Simpul tengah tetap tertaut ke simpul pertama pada bagian tersebut, sehingga list kembali utuh dengan memori tambahan O(1).

def isPalindrome(next, values):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

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

Output yang diharapkan

true