Reorder List

Q: Mengapa membalik paruh kedua list?

Jawaban membaca bagian belakang dari node terakhir hingga node pertama, sedangkan singly linked list hanya berjalan ke depan. Membalik bagian belakang sekali, dalam O(n) , memungkinkan penggabungan berjalan maju pada kedua bagian.

Q: Apa kompleksitas waktu dari Reorder List?

method in-place berjalan dalam waktu O(n) dengan memori tambahan O(1) : mencari bagian tengah, membalik, dan menyelang-selingkan masing-masing mengunjungi setiap node sebanyak jumlah konstan. Menyalin nilai ke dalam array juga membutuhkan waktu O(n) , tetapi memerlukan memori O(n) , sedangkan memajukan tail satu node setiap kali membutuhkan waktu O(n²) .

Q: Di mana bagian tengahnya jika list memiliki jumlah node genap?

Hentikan pointer lambat di node terakhir pada separuh bagian depan. Jika ada enam node, kedua separuh terdiri dari tiga node; jika ada lima, jumlahnya tiga dan dua. Node tambahan itu menjadi akhir jawaban, sesuai dengan posisi nilai tengah dalam urutan.

SedangLinked 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 mengakhiri list, dan head-nya adalah node 0. Node-node tersebut tidak disimpan sesuai urutan list, jadi ikuti tautannya.

Sebut node-node sesuai urutannya dalam list sebagai L0, L1, ..., Lk. Susun ulang list sehingga urutannya menjadi L0, Lk, L1, Lk-1, L2, Lk-2, ...: node pertama, lalu node terakhir, lalu node kedua, lalu node kedua dari belakang, dan seterusnya. Kembalikan nilai-nilai dalam urutan baru tersebut.

Fungsi

reorderList(next: integer-array, values: integer-array) → integer-array

nextinteger-array: indeks node yang ditautkan oleh setiap node, atau -1 untuk node terakhir
valuesinteger-array: nilai yang disimpan oleh setiap node
Mengembalikaninteger-array: nilai dalam urutan list yang disusun ulang

Batasan

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

Contoh

Input: next = [3, 4, -1, 1, 2]values = [1, 3, 5, 2, 4]
Output: [1, 5, 2, 4, 3]
Penjelasan: Dengan mengikuti tautan dari node 0, daftar tersebut terbaca 1, 2, 3, 4, 5. Elemen pertama, terakhir, kedua, dan kedua dari belakang menghasilkan 1, 5, 2, 4, lalu nilai tengah 3 muncul terakhir.

Input: next = [2, 3, 1, -1]values = [10, 30, 20, 40]
Output: [10, 40, 20, 30]
Penjelasan: list mengunjungi node 0, 2, 1, 3 dan membaca 10, 20, 30, 40. Pasangan pertama dan terakhir menghasilkan 10, 40, lalu pasangan di bagian dalam menghasilkan 20, 30.

Input: next = [-1]values = [7]
Output: [7]
Penjelasan: List dengan satu node tidak memiliki apa pun untuk dipindahkan, jadi jawabannya adalah [7].

Pertanyaan lanjutan

Dapatkah kamu mengurutkan ulang tautannya dengan memori tambahan O(1)?

Petunjuk

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

0 dari 3 dibuka

Solusi

Urutan baru bergantian antara bagian depan dan belakang, tetapi singly linked list hanya bergerak maju. Bagi pekerjaan ini menjadi tiga langkah standar pada list: temukan bagian tengah dengan pointer lambat dan cepat, balikkan paruh belakang, lalu jalin kedua paruh secara bergantian satu node setiap kali.

Gerakkan ekor ke depan, satu node setiap kali

Intuisi

Pointer di sini adalah indeks node, dan bergerak maju berarti node = next[node]. Setelah node pertama ada node terakhir, jadi lepaskan node terakhir dan sisipkan setelah node saat ini, lalu ulangi dua node lebih jauh. Untuk 1, 2, 3, 4, 5 hasilnya adalah 1, 5, 2, 3, 4, lalu 1, 5, 2, 4, 3. Berhenti saat kurang dari dua node mengikuti node saat ini.

Mencari node sebelum node terakhir mengharuskan kamu menelusuri hingga akhir pada setiap putaran. Penelusuran berkurang dua node setiap putaran, sekitar n²/4 langkah secara total: empat juta untuk 4000 node.

Algoritma

Tetapkan cur = 0.
Selama setidaknya dua node mengikuti cur, telusuri before dari cur hingga next[next[before]] == -1, sehingga tail = next[before] adalah node terakhir.
Lepaskan node itu dengan next[before] = -1, lalu sisipkan: next[tail] = next[cur] dan next[cur] = tail.
Pindahkan cur ke next[tail] dan ulangi.
Telusuri mulai dari node 0 dan kumpulkan nilainya.

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 result

Salin nilai dan baca dari kedua ujung

Intuisi

array mencapai elemen terakhirnya dalam satu langkah. Salin nilai sesuai urutan list, [1, 2, 3, 4, 5] pada contoh pertama, lalu baca dengan lo dari depan dan hi dari belakang: ambil lo, ambil hi, lalu gerakkan keduanya ke arah tengah selama lo < hi. Hasilnya adalah 1, 5, 2, 4; jika panjangnya ganjil, keduanya bertemu pada 3 di tengah, dan elemen itu ditempatkan terakhir.

Kompleksitas waktunya O(n) dan memori tambahannya O(n), serta tautannya tidak pernah berubah.

Algoritma

Telusuri mulai dari simpul 0 dan tambahkan setiap nilai ke inOrder.
Tetapkan lo = 0 dan hi ke indeks terakhir.
Selama lo < hi, tambahkan inOrder[lo] dan inOrder[hi], lalu naikkan lo dan turunkan hi.
Jika lo == hi, tambahkan nilai tengah.

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 result

Temukan bagian tengah, balik urutan separuh bagian belakang, lalu jalin

Intuisi

Untuk 1, 2, 3, 4, 5, 6, jawabannya adalah 1, 6, 2, 5, 3, 4: separuh depan 1, 2, 3 secara berurutan, diselingi separuh belakang 4, 5, 6 yang dibaca dari belakang. Jadi, potong list di bagian tengah, balik separuh belakang, lalu selang-selingkan.

slow bergerak satu tautan, sedangkan fast bergerak dua tautan, sehingga slow berhenti di node terakhir separuh depan: 3, baik untuk lima maupun enam node. Memotong setelahnya membuat separuh depan memiliki satu node tambahan saat panjangnya ganjil, dan node itu menjadi node terakhir dalam jawaban. Proses selang-seling mengambil satu node dari setiap separuh secara bergantian sampai separuh belakang habis.

Setiap node disentuh beberapa kali dalam jumlah tetap, dengan beberapa indeks sebagai memori. R menyalin vektor tautan saat pertama kali diubah, jadi di R memorinya adalah O(n).

Algoritma

Pindahkan slow satu tautan dan fast dua tautan selama next[fast] dan next[next[fast]] bukan -1.
Tetapkan second = next[slow], lalu next[slow] = -1.
Balikkan list yang dimulai dari second; head barunya adalah prev.
Jalin: selama second bukan -1, tautkan first ke second dan second ke next[first] yang lama, lalu majukan keduanya.
Telusuri mulai dari node 0 dan kumpulkan nilainya.

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

Jebakan dan kasus tepi

Jangan berhenti memotong list di bagian tengah. Tanpa next[slow] = -1, bagian depan masih menunjuk ke bagian belakang, dan setelah diselang-selingkan, list akan berputar kembali ke dirinya sendiri.
Jangan menimpa tautan sebelum menyimpannya. Saat membalik dan menyelang-selingkan, baca next[node] ke dalam variabel terlebih dahulu, atau sisa list akan hilang.
Jangan menyelang-selingkan sampai bagian depan berakhir. Jika panjangnya ganjil, perulangan itu berjalan satu kali lagi saat second bernilai -1, lalu membaca next[-1].
Jangan menganggap urutan array sebagai urutan list. Pada contoh pertama, values adalah [1, 3, 5, 2, 4], tetapi urutan list adalah 1, 2, 3, 4, 5.
Di Lua dan R, indeks array dimulai dari 1. Tetap gunakan indeks node berbasis 0 dan baca next[node + 1].

Pertanyaan yang sering diajukan3

Mengapa membalik paruh kedua list?

Jawaban membaca bagian belakang dari node terakhir hingga node pertama, sedangkan singly linked list hanya berjalan ke depan. Membalik bagian belakang sekali, dalam O(n), memungkinkan penggabungan berjalan maju pada kedua bagian.

Apa kompleksitas waktu dari Reorder List?

method in-place berjalan dalam waktu O(n) dengan memori tambahan O(1): mencari bagian tengah, membalik, dan menyelang-selingkan masing-masing mengunjungi setiap node sebanyak jumlah konstan. Menyalin nilai ke dalam array juga membutuhkan waktu O(n), tetapi memerlukan memori O(n), sedangkan memajukan tail satu node setiap kali membutuhkan waktu O(n²).

Di mana bagian tengahnya jika list memiliki jumlah node genap?

Hentikan pointer lambat di node terakhir pada separuh bagian depan. Jika ada enam node, kedua separuh terdiri dari tiga node; jika ada lima, jumlahnya tiga dan dua. Node tambahan itu menjadi akhir jawaban, sesuai dengan posisi nilai tengah dalam urutan.

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

Tes #1

Tes #2

Tes #3

Argumen

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

Output yang diharapkan

[1, 5, 2, 4, 3]

Reorder List

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Gerakkan ekor ke depan, satu node setiap kali

Salin nilai dan baca dari kedua ujung

Temukan bagian tengah, balik urutan separuh bagian belakang, lalu jalin

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa