Remove Nth Node From End of List

Q: Apa kompleksitas waktu dan ruang untuk menghapus node ke-n dari akhir?

Dibutuhkan waktu O(L) untuk list yang terdiri dari L node, karena kamu harus mencapai bagian akhir untuk mengetahui letak target. Menghitung terlebih dahulu dan metode dua pointer sama-sama menggunakan memori tambahan O(1) . Menyalin nilai ke dalam array menggunakan O(L) .

Q: Apakah solusi dengan dua pointer lebih cepat daripada menghitung panjangnya terlebih dahulu?

Tidak jauh berbeda. Keduanya adalah O(L) , dan dua pointer bergerak kira-kira sebanyak dua kali penelusuran. Keuntungannya, kamu tidak perlu mengetahui panjangnya terlebih dahulu, jadi method ini juga berfungsi pada list yang hanya bisa kamu baca sekali.

SedangLinked list 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.

Hapus node ke-n jika dihitung dari akhir list, dengan node terakhir sebagai node ke-1 dari akhir. Kembalikan nilai node yang tersisa, sesuai urutan list.

Fungsi

removeNthFromEnd(values: integer-array, next: integer-array, n: integer) → integer-array

valuesinteger-array: nilai yang disimpan oleh setiap node
nextinteger-array: indeks node yang ditautkan oleh setiap node, atau -1 untuk node terakhir
ninteger: node yang akan dihapus, dihitung dari akhir, dengan 1 sebagai node terakhir
Mengembalikaninteger-array: nilai yang tersisa sesuai urutan list, kosong ketika satu-satunya node dihapus

Batasan

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

Contoh

Input: values = [5, 9, 2, 7, 6]next = [2, 3, 4, -1, 1]n = 2
Output: [5, 2, 6, 7]
Penjelasan: Dengan mengikuti tautan dari node 0, daftar tersebut terbaca 5, 2, 6, 9, 7. Elemen ke-2 dari akhir adalah 9, di node 1; menghapusnya menyisakan 5, 2, 6, 7.

Input: values = [10, 20, 30, 40]next = [1, 2, 3, -1]n = 4
Output: [20, 30, 40]
Penjelasan: Empat node dan n = 4: node ke-4 dari akhir adalah head. List sekarang dimulai dari node 1 dan berisi 20, 30, 40.

Input: values = [42]next = [-1]n = 1
Output: []
Penjelasan: Satu-satunya node adalah head sekaligus node terakhir. Menghapusnya akan membuat list kosong, jadi jawabannya adalah [].

Pertanyaan lanjutan

Bisakah kamu menemukan dan melepas tautan node dalam satu kali lintasan, tanpa menghitung panjangnya terlebih dahulu?

Petunjuk

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

0 dari 3 dibuka

Solusi

Target dihitung dari akhir, tetapi singly linked list hanya bergerak maju, dan untuk melepaskan sebuah node, kamu harus berada di node sebelumnya. Jaga jarak dua pointer sejauh n node: saat pointer depan mencapai node terakhir, pointer belakang berada tepat sebelum target. Di bawah ini, L adalah jumlah node.

Salin nilai-nilai ke dalam array

Intuisi

Pointer di sini adalah indeks node, dan bergerak maju berarti node = next[node]. Telusuri sekali dan tambahkan setiap nilai ke array: [5, 2, 6, 9, 7] pada contoh pertama. Elemen ke-n dari akhir berada di indeks L-n, di sini 5-2 = 3, yaitu 9. Hapus elemen itu dan kembalikan sisanya.

Algoritma ini berjalan dalam waktu O(L) dan menggunakan memori tambahan O(L), serta tidak pernah mengubah tautan.

Algoritma

Mulai dengan array kosong dan node = 0.
Selama node bukan -1, tambahkan values[node] dan pindah ke next[node].
Hapus entri pada indeks length - n.
Kembalikan array.

def removeNthFromEnd(values, next, n):
    # Write the values out in list order.
    order = []
    node = 0
    while node != -1:
        order.append(values[node])
        node = next[node]
    # Counting from the end, the n-th value sits at index len(order) - n.
    del order[len(order) - n]
    return order

Hitung simpulnya, lalu lepaskan tautannya

Intuisi

Untuk menghapus sebuah node, arahkan tautan dari node sebelumnya melewatinya: next[prev] = next[next[prev]]. Hitung jumlah node dalam penelusuran pertama. Dengan head pada posisi 0, target berada pada posisi L-n, jadi prev berjarak L-n-1 langkah dari head. Pada contoh pertama, dua langkah 0 → 2 → 4 mencapai node 4, dan next[4] = next[1] = 3 menghapus 9.

Saat n = L, targetnya adalah head, yang tidak memiliki node sebelumnya, jadi list dimulai dari next[0], seperti pada contoh kedua. Dua kali penelusuran memerlukan sekitar 2L langkah dan beberapa bilangan bulat dalam memori.

Algoritma

Berjalanlah dari node 0 ke -1 dan hitung jumlah node sebagai L.
Jika n == L, head baru adalah next[0].
Jika tidak, mulai dengan prev di node 0 dan gerakkan sebanyak L-n-1 kali, lalu atur next[prev] = next[next[prev]].
Berjalanlah dari head dan kumpulkan values[node] secara berurutan.

def removeNthFromEnd(values, next, n):
    # First pass: count the nodes.
    length = 0
    node = 0
    while node != -1:
        length += 1
        node = next[node]
    head = 0
    if n == length:
        # The node to remove is the head, so the list starts at its second node.
        head = next[0]
    else:
        # Second pass: stop on the node just before position length - n.
        prev = 0
        for _ in range(length - n - 1):
            prev = next[prev]
        next[prev] = next[next[prev]]  # skip over the removed node
    result = []
    node = head
    while node != -1:
        result.append(values[node])
        node = next[node]
    return result

Dua pointer berjarak n tautan

Intuisi

Majukan fast sebanyak n tautan sementara slow menunggu di head, lalu gerakkan keduanya satu tautan setiap kali. Jaraknya tetap n, jadi saat fast berada di node terakhir (posisi L-1), slow berada di posisi L-1-n, tepat sebelum target. Kamu tidak perlu mengetahui L.

Pada contoh pertama, fast bergerak dari 0 → 2 → 4. Lalu slow bergerak ke 2 dan 4, sementara fast bergerak ke 1 dan 3, node terakhir, dan next[4] = next[1] = 3 menghapus 9.

Karena n ≤ L, fast mencapai -1 selama gerak awalnya hanya ketika n = L, tepat saat head adalah target. Pemeriksaan itu melakukan tugas yang dilakukan node dummy pada object node.

Algoritma

Atur fast = 0 dan gerakkan sebanyak n kali dengan fast = next[fast].
Jika fast == -1, head adalah targetnya: head baru adalah next[0].
Jika tidak, atur slow = 0 dan gerakkan keduanya selama next[fast] != -1.
Atur next[slow] = next[next[slow]].
Telusuri dari head dan kumpulkan values[node] secara berurutan.

def removeNthFromEnd(values, next, n):
    # Send fast n links ahead of slow.
    fast = 0
    for _ in range(n):
        fast = next[fast]
    head = 0
    if fast == -1:
        # Fast fell off the end, so the list has exactly n nodes: remove the head.
        head = next[0]
    else:
        # Move both, keeping the gap. When fast stands on the last node,
        # slow stands just before the node to remove.
        slow = 0
        while next[fast] != -1:
            slow = next[slow]
            fast = next[fast]
        next[slow] = next[next[slow]]  # skip over the removed node
    result = []
    node = head
    while node != -1:
        result.append(values[node])
        node = next[node]
    return result

Jebakan dan kasus tepi

Menghapus entri pada indeks array L-n. Node tidak disimpan sesuai urutan list: pada contoh pertama, values[3] = 7 adalah node terakhir, bukan 9.
Memindahkan kedua pointer sampai fast == -1, bukan sampai next[fast] == -1. slow kemudian berada di node target itu sendiri, dan sebuah node tidak dapat melepaskan dirinya sendiri dari list.
Melupakan kasus head. Saat n = L, fast bernilai -1 setelah mulai dari head, dan membaca next[fast] menyebabkan error. Python membaca next[-1] tanpa memberi tahu, lalu mengembalikan list yang salah.
Mengumpulkan jawaban mulai dari node 0 setelah head dihapus. Mulai penelusuran terakhir dari head yang baru.
Dalam array Lua dan R dimulai dari 1. Pertahankan indeks node berbasis 0 dan baca next[node + 1].

Pertanyaan yang sering diajukan3

Mengapa solusi untuk masalah ini menggunakan node dummy?

Menghapus node mengubah tautan node sebelumnya, sedangkan head tidak memiliki node sebelumnya. Node dummy di depan head memberi setiap node sebuah pendahulu, sehingga satu baris untuk memutus tautan berlaku untuk semua kasus, dan jawaban dimulai dari node berikutnya setelah dummy. Memeriksa apakah pointer di depan sudah melewati akhir list memberikan hasil yang sama tanpa node dummy.

Apa kompleksitas waktu dan ruang untuk menghapus node ke-n dari akhir?

Dibutuhkan waktu O(L) untuk list yang terdiri dari L node, karena kamu harus mencapai bagian akhir untuk mengetahui letak target. Menghitung terlebih dahulu dan metode dua pointer sama-sama menggunakan memori tambahan O(1). Menyalin nilai ke dalam array menggunakan O(L).

Apakah solusi dengan dua pointer lebih cepat daripada menghitung panjangnya terlebih dahulu?

Tidak jauh berbeda. Keduanya adalah O(L), dan dua pointer bergerak kira-kira sebanyak dua kali penelusuran. Keuntungannya, kamu tidak perlu mengetahui panjangnya terlebih dahulu, jadi method ini juga berfungsi pada list yang hanya bisa kamu baca sekali.

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

Tes #1

Tes #2

Tes #3

Argumen

values = [5, 9, 2, 7, 6]
next = [2, 3, 4, -1, 1]
n = 2

Output yang diharapkan

[5, 2, 6, 7]

Remove Nth Node From End of List

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Salin nilai-nilai ke dalam array

Hitung simpulnya, lalu lepaskan tautannya

Dua pointer berjarak n tautan

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa