Cara menggabungkan senarai terpaut tersusun di Jawa

Masalah

Gabungkan dua senarai terpaut menaik ke dalam senarai terpaut menaik baharu dan kembalikan. Senarai terpaut baharu dibentuk dengan menggabungkan semua nod dua senarai terpaut yang diberikan.

Contoh 1:

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

Contoh 2:

8e99a69fbe029cd4e2b854e244eab143Input: 128dba7a3a77be0113eb0bea6ea0a5d0l1 = [], l2 = []
8e99a69fbe029cd4e2b854e244eab143Output: 128dba7a3a77be0113eb0bea6ea0a5d0[]

Contoh 3:

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

Idea

Versi 1

• Buat senarai terpaut kosong nList

• Apabila kedua-dua senarai terpaut (l1, l2) tidak kosong, bandingkan nilai elemen pertama daripada dua senarai terpaut, ambil yang terkecil dan tambahkannya pada yang baharu senarai terpaut Kemudian penuding kepala senarai terpaut kecil menghala ke bit seterusnya, dan penuding nList juga menghala ke bit seterusnya

• Jika kedua-dua senarai terpaut masih belum kosong, teruskan untuk menggelungkan

• Jika salah satu daripada dua senarai terpaut kosong, kemudian sambung senarai terpaut yang tidak kosong di belakang nList

• Akhirnya kembalikan senarai seterusnya nList sebagai ketua senarai terpaut baharu Nod

Versi 2

• mula-mula menentukan sama ada dua senarai terpaut itu kosong dan mengembalikan senarai terpaut kosong secara langsung jika ia kosong. Jika ia tidak kosong, teruskan ke bawah

• Tentukan nod kepala l1 dan l2 yang mana lebih kecil, kemudian simpan nod ini sebagai nod kepala, dan nod seterusnya akan menjadi disambung pada nod ini pada satu masa Di atas.

• Idea berikut adalah sama dengan versi 1

Jawapannya

Versi 1

Buat nod baharu dan gantikan yang asal Senarai terpaut dipindahkan ke senarai terpaut baharu

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode head = new ListNode(-1);
    ListNode   = head;
    while (list1 != null && list2 != null) {
        boolean b = list1.val <= list2.val;
        all.next = b ? list1 : list2;
        if (b) list1 = list1.next;
        else list2 = list2.next;
        all = all.next;
    }
    all.next = list1 != null ? list1 : list2;
    return head.next;
}

Versi 2

Pilih satu daripada senarai terpaut asal untuk penyepaduan, dan tidak digunakan pada mana-mana ingatan baharu

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    if (list1 == null || list2 == null) {
        return list1 == null ? list2 : list1;
    }
    ListNode head = list1.val <= list2.val ? list1 : list2;
    if (list1.val <= list2.val)
        list1 = list1.next;
    else
        list2 = list2.next;
    ListNode tmp = head;
    while (list1 != null && list2 != null) {
        boolean b = list1.val <= list2.val;
        tmp.next = b ? list1 : list2;
        if (b) list1 = list1.next;
        else list2 = list2.next;
        tmp = tmp.next;
    }
    tmp.next = list1 != null ? list1 : list2;
    return head;
}

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