Gabungkan daftar leetcode python yang diurutkan

Tag sudah ada dengan nama cabang yang disediakan. Banyak perintah Git menerima nama tag dan cabang, jadi membuat cabang ini dapat menyebabkan perilaku yang tidak diharapkan. Anda yakin ingin membuat cabang ini?

Suraj Misra

Mengikuti

27 September 2021

·

2 menit membaca

·

Khusus anggota

Gabungkan dua daftar dalam satu daftar yang diurutkan. Daftar harus dibuat dengan menyatukan node dari dua daftar pertama

Kembalikan kepala daftar tertaut yang digabungkan

Contoh 1

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Contoh 2

Input: list1 = [], list2 = []
Output: []

Contoh 3

Input: list1 = [], list2 = [0]
Output: [0]

Kendala

• Jumlah node di kedua daftar berada dalam rentang [0, 50]
• -100 <= Node.val <= 100_
• Baik list1 dan list2 diurutkan dalam urutan tidak menurun

1. Metode Iteratif —

dummy = curr = ListNode()
        
while list1 and list2:
    if list1.val < list2.val:
        curr.next = list1
        list1 = list1.next
    else:
        curr.next = list2
        list2 = list2.next
    curr = curr.next
            
curr.next = list1 or list2
            
return dummy.next

Penjelasan -

Kami mulai dengan membuat simpul boneka yang akan berguna saat mengembalikan daftar yang digabungkan

Sekarang, kita cukup melintasi kedua daftar sampai salah satu atau keduanya habis

Jika nilai saat ini dari node list1 lebih kecil dari nilai node list2 saat ini, kami menambahkan node list1 ke pointer berikutnya curr kami, dan pindah ke node berikutnya di list1

Demikian pula, kami menambahkan node list2 ke pointer berikutnya curr kami, dan pindah ke node berikutnya di list2, jika nilai di list2 lebih kecil

Setelah ini, kami juga memindahkan node saat ini ke node berikutnya

Perulangan while DAPAT berakhir jika kedua daftar habis. Tetapi bagaimana jika kedua daftar itu tidak sama panjangnya?

Kami kemudian mengarahkan penunjuk berikutnya dari simpul curr kami ke daftar yang tersisa, karena kami tahu bahwa itu sudah diurutkan

Akhirnya, kami mengembalikan simpul berikutnya ke simpul dummy kami yang merupakan awal dari daftar gabungan baru kami

Kompleksitas Waktu dan Ruang —

Karena kita melintasi daftar hanya sekali, kita dapat mengatakan bahwa kode kita membutuhkan waktu linier untuk dijalankan

Juga, kami menggunakan jumlah ruang ekstra yang konstan

Jadi, jika m adalah panjang dari list1 dan n adalah panjang dari list2,

Kompleksitas Waktu. O(m+n)

Kompleksitas Ruang. O(1)

2. Metode Rekursif —

if not list1 or not list2:
    return list1 or list2
        
if list1.val < list2.val:
    list1.next = self.mergeTwoLists(list1.next, list2)
    return list1
else:
    list2.next = self.mergeTwoLists(list1, list2.next)
    return list2

Penjelasan -

Kondisi penghentian rekursi kami adalah ketika salah satu dari daftar tersebut telah habis;

Jika nilai node saat ini di list1 lebih kecil dari pada list2, kami memanggil fungsi secara rekursif pada sisa list1 dan seluruh list2 — dan kami menambahkan jawaban ini ke node list1 kami saat ini

Jika tidak, kami memanggil fungsi secara rekursif pada list1 dan sisa list2 — dan kami menambahkan jawaban ini ke node list2 kami saat ini

Dalam kedua kasus, kami mengembalikan simpul yang berisi angka yang lebih kecil

Kompleksitas Waktu dan Ruang —

Karena kita melintasi daftar hanya sekali, kita dapat mengatakan bahwa kode kita membutuhkan waktu linier untuk dijalankan

Juga, karena tumpukan rekursi menyimpan semua elemen di kedua daftar di beberapa titik, kita membutuhkan ruang ekstra dalam jumlah linier

Bagaimana cara menggabungkan dua daftar tertaut yang diurutkan dengan Python?

Bagaimana cara menggabungkan dua daftar yang diurutkan?

Bagaimana cara menggabungkan dua daftar secara berurutan dengan Python?

Apa kerumitan waktu untuk menggabungkan dua daftar yang diurutkan?