Sort List

+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 adalah node 0. Node-node tersebut tidak disimpan sesuai urutan dalam list, dan array mungkin juga menyimpan node sisa yang tidak pernah dicapai saat menelusuri dari node 0. Node-node itu bukan bagian dari list, bahkan ketika tautannya mengarah ke dalam list.

Urutkan list berdasarkan nilai secara tidak menurun dan kembalikan nilai node-node tersebut dalam urutan itu.

Fungsi

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

nextinteger-array: indeks node yang dituju setiap node, atau -1 untuk node terakhir
valuesinteger-array: nilai yang disimpan oleh setiap node
Mengembalikaninteger-array: nilai node list, dari yang terkecil terlebih dahulu

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 mencapai -1 tanpa mengunjungi node yang sama dua kali.
Node yang tidak dapat dijangkau oleh penelusuran dari node 0 bukan bagian dari list. Entri next-nya dapat menunjuk ke mana saja.

Contoh

Input: next = [3, -1, 4, 2, 1]values = [4, 1, 3, 2, 5]
Output: [1, 2, 3, 4, 5]
Penjelasan: Penelusuran dari node 0 mengunjungi node 0, 3, 2, 4, 1, jadi list tersebut berisi 4, 2, 3, 5, 1. Setelah diurutkan, hasilnya adalah 1, 2, 3, 4, 5.

Input: next = [2, 0, -1, -1]values = [6, 9, -2, 5]
Output: [-2, 6]
Penjelasan: list tersebut adalah 0 → 2, yang berarti 6, -2. Node 1 dan 3 tidak pernah dicapai dari head, jadi nilainya 9 dan 5 tidak disertakan, meskipun node 1 terhubung ke node 0.

Input: next = [1, 2, 3, -1]values = [3, -1, 3, -1]
Output: [-1, -1, 3, 3]
Penjelasan: list tersebut berisi 3, -1, 3, -1. Nilai yang sama tetap ada dalam jawaban sebanyak kemunculannya: -1, -1, 3, 3.

Pertanyaan lanjutan

Bisakah kamu mengurutkan dengan menyambungkan ulang node dalam waktu O(n log n), tanpa menyalin nilai-nilainya?

Solusi

Quicksort dan heapsort mengandalkan akses acak, sedangkan singly linked list hanya bergerak maju. Merge sort cocok: membagi list di bagian tengahnya dan menggabungkan dua list yang sudah terurut sama-sama dilakukan dengan bergerak maju, sehingga algoritma ini mengurutkan tautannya sendiri dalam O(n log n). Di sini, n adalah panjang array.

Salin nilai-nilainya ke dalam array lalu urutkan

Intuisi

list adalah nilai apa pun yang dikunjungi oleh penelusuran node = next[node] dari node 0 hingga -1. Kumpulkan nilai-nilai itu ke dalam array baru, urutkan dengan fungsi pengurutan bawaan, lalu kembalikan hasilnya. Kamu tidak bisa langsung mengurutkan values: pada contoh kedua, variabel itu berisi 9 dan 5, yang tidak ada dalam list.

Penelusuran ini memerlukan waktu O(n) dan pengurutan memerlukan waktu O(n log n), dengan memori tambahan O(n). list itu sendiri tidak pernah disentuh, itulah sebabnya pewawancara meminta pendekatan berikutnya.

Algoritma

Mulai dengan array kosong dan node = 0.
Selama node bukan -1, tambahkan values[node] lalu pindah ke next[node].
Urutkan array dari kecil ke besar dan kembalikan array tersebut.

def sortList(next, values):
    # Collect the values of the nodes on the list, then sort them.
    on_list = []
    node = 0
    while node != -1:
        on_list.append(values[node])
        node = next[node]
    on_list.sort()
    return on_list

Merge sort pada tautan

Intuisi

Pointer lambat yang bergerak satu tautan dan pointer cepat yang bergerak dua tautan menemukan bagian tengah dalam satu kali penelusuran. Menggabungkan dua list terurut hanya membutuhkan node terdepannya: ambil yang lebih kecil, lalu lanjutkan ke node berikutnya. Kedua langkah ini tidak membutuhkan array kedua.

Pada contoh pertama, slow berhenti di 3, dan memutus tautannya membagi 4, 2, 3, 5, 1 menjadi 4, 2, 3 dan 5, 1. Keduanya diurutkan menjadi 2, 3, 4 dan 1, 5, lalu penggabungan mengambil 1, 2, 3, 4, kemudian menautkan sisa 5.

Setiap tingkat pemisahan menyentuh setiap node sejumlah kali yang konstan, dan ada sekitar log n tingkat, jadi waktunya adalah O(n log n). Satu-satunya memori tambahan adalah stack rekursi, dengan kedalaman sekitar 12 pemanggilan untuk 4000 node.

Algoritma

Jika list memiliki satu node (next[head] == -1), kembalikan head.
Mulai dengan slow = head dan fast = next[head]; gerakkan slow satu tautan dan fast dua tautan selama fast dan next[fast] bukan -1.
Tetapkan second = next[slow] dan putuskan tautannya dengan next[slow] = -1.
Urutkan kedua bagian secara rekursif. Gabungkan keduanya: tautkan node terdepan yang lebih kecil setelah tail sampai salah satu bagian kosong, lalu tautkan sisa bagian lainnya.
Telusuri dari head yang dikembalikan dan kumpulkan nilainya.

def sortList(next, values):
    def merge(a, b):
        # Splice two sorted lists into one; on a tie the node from a goes first.
        head = tail = -1
        while a != -1 and b != -1:
            if values[b] < values[a]:
                node, b = b, next[b]
            else:
                node, a = a, next[a]
            if tail == -1:
                head = node
            else:
                next[tail] = node
            tail = node
        next[tail] = a if a != -1 else b  # attach whatever is left
        return head

    def sort(head):
        if next[head] == -1:  # one node is already sorted
            return head
        # slow stops on the last node of the first half
        slow, fast = head, next[head]
        while fast != -1 and next[fast] != -1:
            slow = next[slow]
            fast = next[next[fast]]
        second = next[slow]
        next[slow] = -1  # cut the list in two
        return merge(sort(head), sort(second))

    result = []
    node = sort(0)
    while node != -1:
        result.append(values[node])
        node = next[node]
    return result

Jebakan dan kasus tepi

Mengurutkan seluruh array values. Pada contoh kedua, langkah ini memasukkan 9 dan 5, yang tidak ada di list.
Memulai fast di head. Dengan dua node, slow kemudian berada di node kedua, pemotongan membuat paruh kedua kosong, dan rekursi tidak pernah mengecil.
Lupa melakukan pemotongan next[slow] = -1. Paruh pertama kemudian berlanjut ke paruh kedua, dan kedua pemanggilan mengurutkan list yang saling tumpang tindih.
Membuang sisa paruh saat paruh lainnya habis. Node-node itu hilang dari hasil.
Di Lua dan R, array dimulai dari 1: pertahankan indeks node berbasis 0 dan baca next[node + 1]. Versi R menyalin array tautan sekali, jadi menggunakan memori tambahan O(n).

Pertanyaan yang sering diajukan3

Apa cara terbaik untuk mengurutkan linked list?

Merge sort. Membagi di bagian tengah, mengurutkan kedua bagian, lalu menggabungkannya, semuanya dilakukan dengan menelusuri list ke depan, satu-satunya arah yang didukung oleh singly linked list. Algoritma ini berjalan dalam waktu O(n log n) dan menautkan ulang node yang sudah ada.

Mengapa merge sort lebih disukai daripada quicksort untuk linked list?

Quicksort dapat membagi list dengan menyambungkan ulang, tetapi pivot yang baik membutuhkan akses acak, dan menjadikan elemen pertama sebagai pivot membuat list yang sudah terurut memerlukan O(n²). Merge sort selalu membagi list menjadi dua, sehingga kompleksitasnya tetap O(n log n) untuk input apa pun.

Bisakah kamu mengurutkan linked list dalam waktu O(n log n) dan menggunakan memori O(1)?

Ya, dengan merge sort bottom-up. Algoritma ini menggabungkan segmen yang bersebelahan dengan panjang 1, lalu 2, lalu 4, hingga satu segmen mencakup seluruh list. Ada log n lintasan linear, dan satu-satunya memori yang digunakan hanyalah beberapa indeks node.

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

Tes #1

Tes #2

Tes #3

Argumen

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

Output yang diharapkan

[1, 2, 3, 4, 5]