Gabungkan senarai tersusun

Hari ini, kita melihat satu lagi tugas senarai terpaut.

Buat fungsi untuk menggabungkan 2 senarai terpaut yang diisih. Senarai yang terhasil hendaklah senarai diisih menggunakan nod 2 senarai.

Untuk ini, kami akan menggunakan pelaksanaan senarai pautan generik dari siaran sebelumnya yang boleh didapati di sini

func mergeSortedLists(ll1 LinkedList[int], ll2 LinkedList[int]) LinkedList[int] {
    result := LinkedList[int]{}

    p1 := ll1.Head
    p2 := ll2.Head
    rp := &Node[int]{} // dummy node as result head
    result.Head = rp
    for p1 != nil && p2 != nil {
        if p1.Data >= p2.Data {
            rp.Next = p2
            p2 = p2.Next
        } else {
            rp.Next = p1
            p1 = p1.Next
        }
        rp = rp.Next
    }
    if p1 != nil {
        rp.Next = p1
    }
    if p2 != nil {
        rp.Next = p2
    }
    result.Head = result.Head.Next
    return result
}

Logiknya agak mudah untuk diikuti. Mula-mula, kami menyediakan penunjuk ke kepala 2 senarai dan senarai yang terhasil. Memandangkan kami tidak mengetahui 'kepala' senarai yang terhasil, kami mencipta nod tiruan sebagai pemegang tempat (kami akan membetulkannya kemudian). Kami juga mencipta nod semasa, rp, untuk senarai hasil.

Seterusnya, kami mengulangi 2 senarai tersebut. Kami mempunyai nod semasa untuk setiap senarai. Pada setiap langkah, kita melihat mana antara 2 nod semasa mempunyai nilai yang lebih kecil dan meletakkan nod itu pada senarai hasil. Kemudian alihkan nod semasa senarai itu (yang lebih kecil) ke nod seterusnya dalam senarai. Kami juga perlu mengalihkan nod semasa hasil ke tempat seterusnya.

Logik gelung kami adalah untuk terus melakukan ini sehingga kami sampai ke penghujung salah satu senarai. Pada ketika ini, kita tahu bahawa tiada lagi elemen untuk dibandingkan untuk salah satu senarai; mereka sudah berada dalam senarai keputusan. Jadi, kita boleh meletakkan baki nod senarai lain pada penghujung hasil, kerana kita tahu ia sudah diisih.

Bagaimana anda akan melakukan ini berbeza? Bolehkah kita mengoptimumkan ini? Beritahu saya dalam ulasan.

Terima kasih!

Kod untuk siaran ini dan semua siaran dalam siri ini boleh didapati di sini

Atas ialah kandungan terperinci Gabungkan senarai tersusun. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!