Python menggabungkan dua daftar yang diurutkan

Gabungkan dua daftar terurut yang diurutkan dan kembalikan sebagai daftar terurut yang baru. Daftar baru harus dibuat dengan menyatukan node dari dua daftar pertama

Kendala

• Jumlah node di kedua daftar berada dalam kisaran [0, 50]
• -100 ≤ Node.val ≤ 100
• Baik l1 dan l2 diurutkan dalam urutan tidak menurun

Contoh

Contoh 1

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

Contoh 2

Input: l1 = [], l2 = []
Output: []

Contoh 3

Input: l1 = [], l2 = [0]
Output: [0]

Analisis

Kami akan diberikan dua daftar terurut yang diurutkan, dan kami perlu menggabungkannya sedemikian rupa sehingga daftar yang dihasilkan juga akan diurutkan. Daftar diurutkan dalam urutan yang tidak menurun, oleh karena itu, daftar yang dihasilkan juga harus dalam urutan yang tidak menurun

Mendekati

Pendekatannya cukup lurus ke depan. Jika Anda pernah bekerja dengan Merge Sort sebelumnya, itu mirip dengan itu. Kami akan menggunakan fungsi gabungan dari jenis gabungan untuk menyelesaikan masalah ini. Langkah-langkahnya adalah -

1. Periksa apakah ada daftar yang kosong
2. Pertama kita perlu menentukan kepala dari daftar yang dihasilkan. Kepala ini akan lebih kecil dari kepala daftar yang diberikan
3. Ulangi setiap node daftar sampai salah satu daftar dilintasi sepenuhnya
4. Saat melintasi daftar, identifikasi simpul yang lebih kecil dari daftar dan tambahkan ke daftar yang dihasilkan
5. Setelah loop selesai, mungkin ada kasus di mana daftar memiliki node yang tersisa. Kami akan menambahkan simpul yang tersisa ke daftar yang dihasilkan

Jika jumlah node adalah m dan n di kedua daftar, maka kompleksitas waktu keseluruhan akan menjadi O(m + n) karena kita melintasi semua node dari kedua daftar

Kompleksitas Ruang

Kami membuat daftar untuk menyimpan hasil kami, tetapi kami tidak menggunakannya sebagai bagian dari perhitungan perantara kami, maka kompleksitas ruang menurut saya adalah O(1)

Jawa

Piton

JavaScript

Kotlin

Kode Lengkap

Kesimpulan

Selamat 👏. Kami telah memecahkan masalah menggunakan fungsi gabungan dari jenis gabungan

Saya harap anda menikmati postingan ini. Jangan ragu untuk membagikan pemikiran Anda tentang hal ini

Anda dapat menemukan kode sumber lengkap di repositori GitHub saya. Jika Anda menyukai apa yang Anda pelajari, silakan garpu 🔪 dan beri bintang ⭐

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 kisaran [0, 50]
• -100 <= Node.val <= 100
• Baik list1 dan list2 diurutkan dalam urutan tidak menurun

Larutan. →

Di sini, kita perlu mengikuti langkah-langkah di bawah ini, Mari saya tunjukkan dengan gambar

1. Periksa apakah ada daftar tertaut yang kosong. Jika ya maka kembalikan yang lain

2. Sekarang di sini kita akan mengambil dua daftar tertaut lainnya, yang pertama adalah kepala dan satu lagi adalah temp, di sini temp akan digunakan untuk mengisi daftar tertaut yang dihasilkan, kepala akan menjadi simpul pertama (kepala) dari daftar tertaut temp

3. Kami memiliki dua daftar tertaut (list1, list2), misalkan ini diisi dengan nilai di bawah ini

4. Karena kita perlu mendapatkan linked list dalam urutan menaik, kita akan mengisi linked list dengan nilai terendah, jadi kita akan memeriksa, dari dua linked list mana linked list yang memiliki nilai terendah pada node pertama

5. Berikut daftar1. val dan daftar2. val keduanya memiliki 1

6. Jadi kita akan mengambil list1. val dan tambahkan ke head dan temp linked list

7. Setelah mengisi data dari list1 ke temp serta head linked list, kita pindah ke node berikutnya dari list1,

8. Sekarang kita pindah ke kondisi lain yaitu while loop, disini kita akan melakukan transversal sampai kedua linked list mencapai tail (end)

9. Sekarang seperti langkah di atas. 5, kita cek linked list mana yang nilainya lebih kecil, kita isikan dulu. Di sini list2 memiliki nilai 1 yang lebih kecil dari nilai list1 yaitu 2

Kami akan menambahkan nilai itu ke node berikutnya dari temp linked list

10. Karena kami mendapatkan nilai dari list2, sekarang kami bergerak maju di linked list2 atau Anda dapat mengatakan, kami menunjuk ke node berikutnya dari list2

11. Setelah itu kami menunjuk ke node temp berikutnya

12. Sekarang, sekali lagi kami mengulangi langkah-langkah itu, node mana yang memiliki nilai lebih kecil, kami akan menambahkannya ke node temp linked list berikutnya, seperti gambar di bawah ini

13. Sesuai gambar di atas, list1 memiliki nilai lebih kecil yaitu 2, jadi kami menambahkan ke daftar tertaut temp

14. Sekarang kita bergerak maju di node berikutnya dari linked list1 yaitu 4

15. Sekarang, kita bergerak maju dalam daftar tautan temp

16. Sesuai gambar di atas, list2 memiliki nilai lebih kecil yaitu 3, jadi kami menambahkan ke node berikutnya dari daftar tertaut temp

17. Sekarang kita bergerak maju di node berikutnya dari linked list2 yaitu 5

18. Sekarang, kita bergerak maju dalam daftar tautan temp

19. Sesuai gambar di atas, list1 memiliki nilai lebih kecil yaitu 4, jadi kami menambahkan ke node berikutnya dari daftar tertaut temp

20. Sekarang kita bergerak maju di node berikutnya dari list1 yang ditautkan yaitu NULL

21. Sekarang, kita bergerak maju dalam daftar tautan temp

22. Sekarang, list1 menunjuk ke NULL dan list2 menunjuk ke beberapa nilai. Jadi seperti halnya jika kondisi kita menambahkan nilai list2 yaitu 5 ke node temp linked list berikutnya

23. Sekarang kita bergerak maju di node berikutnya dari linked list2 yaitu NULL

24. Sekarang, kita bergerak maju dalam daftar tautan temp

25. Sekarang list1 poin NULL dan list2 poin ke NULL, kedua daftar tertaut tercapai di akhir, jadi di sini while loop akan menjadi salah dan akan diakhiri

26. Ini adalah daftar tertaut tunggal, kami tidak dapat kembali, jadi kami perlu mengembalikan HEAD (yang menunjuk ke node pertama dari daftar tertaut temp), sebagai jawaban

Jadi, inilah solusinya. Sekarang kita bergerak maju ke seluruh bagian kode

Kode (Jawa). →

Kode (Python). →

Jika jumlah node adalah m dan

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

Kami membuat daftar tertaut untuk menyimpan hasil kami, maka kompleksitas ruang menurut saya adalah O(m + n)

Bagaimana cara menggabungkan dua daftar yang diurutkan dengan Python?

Bagaimana cara menggabungkan dua daftar dan mengurutkannya?

Bagaimana cara menggabungkan dua array dalam urutan terurut dengan Python?

Apa 3 cara berbeda untuk menggabungkan 2 daftar dengan Python?