Reverse Linked List

+10

Kamu mendapatkan singly linked list yang disimpan dalam array next: node i 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.

Balik list dengan membalik setiap tautan, sehingga node terakhir yang lama menjadi head dan node 0 menjadi node terakhir yang terhubung ke -1. Kembalikan array next yang telah diperbarui, dengan panjang yang sama seperti input.

Fungsi

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

nextinteger-array: indeks simpul yang ditautkan oleh setiap simpul, atau -1 untuk simpul terakhir
Mengembalikaninteger-array: array berikutnya dari list yang dibalik

Batasan

1 ≤ next.length ≤ 5000
Setiap next[i] adalah -1 atau indeks node dari 0 hingga next.length-1.
Mulai dari node 0, list mengunjungi setiap node tepat satu kali lalu mencapai -1. Tidak ada siklus.

Contoh

Input: next = [1, 2, 3, -1]
Output: [-1, 0, 1, 2]
Penjelasan: Jika dibalik, 0 → 1 → 2 → 3 menjadi 3 → 2 → 1 → 0: setiap node terhubung ke node sebelumnya, dan node 0 terhubung ke -1.

Input: next = [2, -1, 3, 1]
Output: [-1, 3, 0, 2]
Penjelasan: Dalam urutan terbalik, 0 → 2 → 3 → 1 menjadi 1 → 3 → 2 → 0. Setiap tautan baru berada pada indeks node-nya: [-1, 3, 0, 2], bukan array yang dibalik [1, 3, -1, 2].

Input: next = [-1]
Output: [-1]
Penjelasan: Satu node adalah kebalikan dari dirinya sendiri. Node itu tetap menjadi head dan tail, dan tetap terhubung ke -1.

Pertanyaan lanjutan

Bisakah kamu membalik hanya bagian list di antara posisi left dan posisi right, serta membiarkan node sebelum dan sesudahnya tetap di tempatnya?

Petunjuk

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

0 dari 3 dibuka

Solusi

Membalik list tidak memindahkan node mana pun, tetapi membalik arah setiap tautan. Tautan pada node adalah satu-satunya jalanmu menuju bagian list lainnya, jadi begitu kamu menimpanya, semua bagian setelahnya akan hilang. Catat urutannya terlebih dahulu, atau telusuri list sekali dan simpan arah ke depan sebelum membalik setiap tautan.

Catat urutannya, lalu tautkan kembali

Intuisi

Pointer di sini adalah indeks node, dan untuk bergerak maju gunakan node = next[node]. Telusuri dari node 0 hingga -1 dan catat node-node tersebut: [0, 2, 3, 1] pada contoh kedua. Dalam list yang dibalik, setiap node terhubung ke node sebelumnya dalam urutan tersebut, dan head lama terhubung ke -1. Tulis tautan tersebut ke array baru agar tidak ada yang tertimpa saat kamu masih membutuhkannya.

Proses ini memerlukan waktu O(n) dan memori tambahan O(n) untuk urutan dan array baru.

Algoritma

Berjalanlah dari node 0 ke -1 dan tambahkan setiap node ke order.
Buat array baru dengan panjang yang sama.
Atur entri order[0] menjadi -1.
Untuk setiap k ≥ 1, atur entri order[k] menjadi order[k-1].
Kembalikan array baru.

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

Balik arah tautan dalam satu kali proses

Intuisi

Balikkan setiap tautan saat kamu mencapai nodenya, dan ingat node asalmu di prev. Nilainya dimulai dari -1, karena head lama menjadi node terakhir. Menetapkan next[node] = prev akan menghapus satu-satunya jalanmu ke depan, jadi simpan dulu di after.

Setiap saat, node-node di belakangmu membentuk list terbalik yang diawali oleh prev, dan node-node di depanmu belum disentuh, dimulai dari node. Saat node mencapai -1, setiap tautan sudah dibalik dan prev menjadi head baru. Pada contoh kedua, proses penelusuran menulis next[0] = -1, next[2] = 0, next[3] = 2 dan next[1] = 3.

Setiap node dikunjungi sekali, dengan waktu O(n) dan menggunakan memori sebesar tiga bilangan bulat.

Algoritma

Tetapkan prev = -1 dan node = 0.
Selama node bukan -1, simpan after = next[node].
Tetapkan next[node] = prev.
Lanjutkan: prev = node, lalu node = after.
Kembalikan next.

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

Jebakan dan kasus tepi

Menimpa next[node] sebelum menyimpannya. Tautan maju yang lama hilang, dan penelusuran bergerak mundur alih-alih menuju node berikutnya.
Memulai prev dari 0, bukan -1. Node 0 kemudian tertaut ke dirinya sendiri.
Membalik array alih-alih tautannya. [2, -1, 3, 1] menjadi [1, 3, -1, 2], bukan [-1, 3, 0, 2].
Melakukan perulangan selama next[node] != -1. Tautan node terakhir tidak pernah dibalik. Lakukan perulangan selama node != -1.
Di Lua dan R, indeks array dimulai dari 1. Tetap gunakan indeks node berbasis 0 dan baca next[node + 1].

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu dan ruang untuk membalik linked list?

Versi iteratif mengunjungi setiap node satu kali, dengan waktu O(n), dan menggunakan tiga pointer, dengan ruang tambahan O(1). Menyalin urutannya ke dalam array terlebih dahulu juga memerlukan waktu O(n), tetapi membutuhkan ruang tambahan O(n). Versi rekursif menggunakan ruang O(n) untuk tumpukan pemanggilan.

Bisakah kamu membalik linked list secara rekursif?

Ya. Balikkan semua node setelah head, lalu buat node berikutnya yang lama dari head menunjuk kembali ke head dan atur tautan head agar kosong. Cara ini mudah dibaca, tetapi membuat satu pemanggilan bersarang untuk setiap node, sehingga list yang panjang dapat membuat call stack meluap. Python berhenti pada 1000 pemanggilan secara default, jumlah yang terlampaui oleh list dengan 5000 node.

Mengapa membalik linked list memerlukan tiga pointer?

Untuk membalik tautan sebuah node, kamu memerlukan node itu sendiri dan node sebelumnya, yaitu dua pointer. Pointer ketiga menyimpan node sesudahnya, karena membalik tautan menghapus satu-satunya referensi ke bagian list lainnya. Tanpanya, penelusuran tidak dapat dilanjutkan.

def reverseList(next):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

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

Output yang diharapkan

[-1, 0, 1, 2]