Merge Two Sorted Lists

Q: Apa kompleksitas waktu untuk menggabungkan dua list yang sudah diurutkan?

Kompleksitasnya adalah O(L1 + L2) : setiap perbandingan menempatkan satu node, dan tidak ada node yang ditempatkan dua kali. Dengan object node, proses penggabungan membutuhkan memori tambahan sebesar O(1) , karena hanya mengubah tautan. Dengan array yang digunakan di sini, array tautan bersama membutuhkan memori sebesar O(L1 + L2) .

MudahLinked list Two pointers

+10

Kamu mendapatkan dua linked list satu arah, masing-masing disimpan dalam dua array yang panjangnya sama. Dalam list pertama, node i menyimpan nilai values1[i] dan terhubung ke node next1[i]. List kedua bekerja dengan cara yang sama menggunakan next2 dan values2. Dalam kedua list, -1 menandai akhir list dan head-nya adalah node 0. Node-node tersebut tidak disimpan sesuai urutan list, jadi ikuti tautannya.

Setiap list diurutkan dalam urutan tidak menurun sepanjang tautannya. Gabungkan keduanya menjadi satu list terurut dan kembalikan nilai-nilainya sesuai urutan.

Fungsi

mergeTwoLists(next1: integer-array, values1: integer-array, next2: integer-array, values2: integer-array) → integer-array

next1integer-array: indeks simpul yang ditautkan oleh setiap simpul dalam list pertama, atau -1 untuk simpul terakhirnya
values1integer-array: nilai yang disimpan oleh setiap node dalam list pertama
next2integer-array: indeks node yang ditautkan oleh setiap node pada list kedua, atau -1 untuk node terakhirnya
values2integer-array: nilai yang disimpan oleh setiap node dalam list kedua
Mengembalikaninteger-array: nilai dari list yang digabungkan, secara berurutan

Batasan

1 ≤ L1 ≤ 2000, di mana L1 adalah panjang next1 dan values1.
1 ≤ L2 ≤ 2000, dengan L2 adalah panjang next2 dan values2.
-1000 ≤ values1[i], values2[j] ≤ 1000
Setiap entri next1 adalah -1 atau indeks node dari list pertama, dan setiap entri next2 adalah -1 atau indeks node dari list kedua.
Dimulai dari node 0, setiap list mengunjungi semua node-nya tepat satu kali, lalu mencapai -1. Tidak ada siklus.
Di sepanjang tautannya, setiap list diurutkan dalam urutan tidak menurun.

Contoh

Input: next1 = [2, -1, 1]values1 = [1, 6, 4]next2 = [3, 2, -1, 1]values2 = [2, 7, 9, 3]
Output: [1, 2, 3, 4, 6, 7, 9]
Penjelasan: Dengan mengikuti tautan, list pertama mengunjungi node 0, 2, 1 dan membaca 1, 4, 6; list kedua membaca 2, 3, 7, 9. Dengan mengambil nilai terdepan yang lebih kecil setiap kali, hasilnya adalah 1, 2, 3, 4, 6, 7, 9.

Input: next1 = [2, -1, 1]values1 = [-3, 5, 0]next2 = [-1]values2 = [0]
Output: [-3, 0, 0, 5]
Penjelasan: List pertama berisi -3, 0, 5 dan list kedua hanya berisi nilai 0. Kedua nilai 0 tetap ada dalam hasil, jadi hasilnya memiliki empat nilai.

Input: next1 = [1, -1]values1 = [8, 10]next2 = [2, -1, 1]values2 = [1, 3, 2]
Output: [1, 2, 3, 8, 10]
Penjelasan: list kedua berisi 1, 2, 3, semuanya lebih kecil daripada 8 yang mengawali list pertama. Seluruh list kedua muncul lebih dahulu, lalu 8, 10.

Pertanyaan lanjutan

Bisakah kamu menggabungkan k list yang sudah diurutkan dalam waktu O(N log k), dengan N sebagai jumlah total simpul?

Petunjuk

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

0 dari 3 dibuka

Solusi

Kedua list sudah diurutkan, jadi nilai terkecil yang tersisa selalu berada di bagian depan salah satunya. Bandingkan kedua bagian depan, tautkan yang lebih kecil ke hasil, lalu maju satu langkah di list itu. Mengurutkan semua nilai N = L1 + L2 juga bisa, tetapi cara itu mengabaikan urutan tersebut dan membutuhkan biaya O(N log N).

Masukkan setiap nilai ke dalam satu array lalu urutkan

Intuisi

List hasil penggabungan adalah versi terurut dari semua nilai N, jadi salin kedua array nilai ke dalam satu array lalu urutkan. Urutan node di dalam array tidak penting, karena pengurutan menempatkan setiap nilai. Dengan N ≤ 4000, ini cukup cepat, tetapi pengurutan memerlukan O(N log N) perbandingan, sedangkan penggabungan memerlukan paling banyak N-1, dan pengurutan tidak pernah menyentuh tautan, keterampilan yang diuji oleh soal ini.

Algoritma

Salin values1 dan values2 ke dalam satu array.
Urutkan array dalam urutan tidak menurun.
Kembalikan array tersebut.

def mergeTwoLists(next1, values1, next2, values2):
    # Sorting puts every value in its place without following a single link.
    return sorted(values1 + values2)

Sisipkan node setelah head dummy

Intuisi

Pointer di sini adalah indeks node. Untuk menautkan node dari kedua list menjadi satu rantai, beri semuanya satu penomoran: node j dari list 2 menjadi node L1+j, dengan tautannya digeser dengan cara yang sama. Node dummy bernomor L1+L2 berada di depan hasilnya.

Pertahankan a dan b pada node pertama yang belum digunakan dari setiap list, serta tail di ujung rantai hasil penggabungan. Pada setiap langkah, tautkan tail ke bagian depan yang lebih kecil, lalu geser pointer tersebut dan tail ke depan. Saat salah satu list habis, sisa list lainnya sudah terurut dan tertaut, jadi cukup satu assignment untuk menautkannya. Pada contoh pertama, list 2 menjadi node 3 hingga 6. Setelah node 0, 3, 6, 2, 1, list 1 habis dan link[tail] = 4 menautkan 7, 9.

Setiap node ditautkan paling banyak satu kali: waktu O(N). Array link bersama membutuhkan memori O(N), sedangkan object node tidak membutuhkan memori.

Algoritma

Buat satu array tautan: next1, lalu next2 yang digeser sebesar L1 (biarkan -1 apa adanya), lalu -1 untuk dummy L1+L2. Buat nilai yang cocok.
Atur a = 0, b = L1, dan tail ke dummy.
Selama a maupun b bukan -1, tautkan tail ke nilai yang lebih kecil (a jika sama), majukan penunjuk tersebut, lalu pindahkan tail ke sana.
Tautkan tail ke a atau b yang bukan -1.
Telusuri dari link[dummy] hingga -1, lalu kumpulkan nilainya.

def mergeTwoLists(next1, values1, next2, values2):
    n1 = len(next1)
    n2 = len(next2)
    # One node space: list 2's node j becomes node n1 + j, and node n1 + n2 is a
    # dummy that sits in front of the merged list.
    link = list(next1) + [j + n1 if j != -1 else -1 for j in next2] + [-1]
    value = list(values1) + list(values2)
    dummy = n1 + n2
    tail = dummy  # the last node of the merged list so far
    a = 0  # the first unused node of list 1
    b = n1  # the first unused node of list 2
    while a != -1 and b != -1:
        if value[a] <= value[b]:
            link[tail] = a  # splice a in after the tail
            a = link[a]
        else:
            link[tail] = b  # splice b in after the tail
            b = link[b]
        tail = link[tail]
    # One list ran out. The rest of the other one is sorted and linked already.
    link[tail] = a if a != -1 else b
    merged = []
    node = link[dummy]
    while node != -1:
        merged.append(value[node])
        node = link[node]
    return merged

Jebakan dan kasus tepi

Menggabungkan array berdasarkan urutan indeks. Node disimpan dalam urutan acak, jadi values1 sendiri tidak terurut: pada contoh pertama, nilainya adalah [1, 6, 4]. Hanya penelusuran mulai dari node 0 yang terurut.
Melupakan sisa nilai. Saat salah satu list kehabisan nilai, perulangan berhenti. Jika sisa nilai dari list lainnya dibuang, nilai terbesar akan hilang: 7, 9 pada contoh pertama.
Menggeser pointer yang salah, atau keduanya. Hanya list yang nodenya kamu ambil yang maju.
Mencampur kedua penomoran. Node 2 dari list 2 bukan node 2 dari list 1. Geser indeks dan tautan list 2 sebesar L1, dan biarkan -1 tetap seperti semula.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu untuk menggabungkan dua list yang sudah diurutkan?

Kompleksitasnya adalah O(L1 + L2): setiap perbandingan menempatkan satu node, dan tidak ada node yang ditempatkan dua kali. Dengan object node, proses penggabungan membutuhkan memori tambahan sebesar O(1), karena hanya mengubah tautan. Dengan array yang digunakan di sini, array tautan bersama membutuhkan memori sebesar O(L1 + L2).

Mengapa menggunakan node dummy saat menggabungkan linked list?

Tanpanya, node pertama dari hasil memerlukan kode tersendiri karena belum ada tail untuk menyambungkannya. Dummy adalah head placeholder, sehingga node pertama disambungkan dengan cara yang sama seperti node lainnya. Di akhir, kamu mengembalikan node next milik dummy dan placeholder tersebut menghilang.

Apakah kamu sebaiknya menggabungkan dua list yang sudah terurut secara rekursif atau iteratif?

Versi rekursif ini singkat: head yang lebih kecil menunjuk ke hasil penggabungan semua elemen lainnya. Namun, versi ini menggunakan satu stack frame untuk setiap node, sehingga list dengan beberapa ribu node dapat menyebabkan stack overflow dalam beberapa bahasa. Perulangan iteratif dengan pointer tail melakukan pekerjaan yang sama dengan penggunaan ruang stack yang konstan.

def mergeTwoLists(next1, values1, next2, values2):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

next1 = [2, -1, 1]
values1 = [1, 6, 4]
next2 = [3, 2, -1, 1]
values2 = [2, 7, 9, 3]

Output yang diharapkan

[1, 2, 3, 4, 6, 7, 9]