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
Menggabungkan Daftar Terurut (Solusi Untuk Masalah Leetcode #21)
Solusi Java untuk https. //kode leet. com/problems/merge-two-sorted-lists/
Awalnya diterbitkan di https. //asyncq. com
Video Youtube
Jika Anda lebih suka format video. https. // www. Youtube. com/watch?v=29RWY7bEq-g
Memahami Masalah
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
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