Gabungkan dua senarai terpaut yang diisih dalam cara mudah dan optimum java

Menggabungkan dua senarai terpaut yang diisih ialah masalah biasa yang boleh diselesaikan dengan cekap. Begini cara anda boleh melakukannya dengan cara yang mudah dan optimum menggunakan Java.

Langkah-langkah:

1. Buat Nod Dummy: Gunakan nod tiruan untuk membantu memudahkan proses cantuman. Nod ini akan berfungsi sebagai permulaan senarai yang digabungkan.
2. Bandingkan Nod: Bandingkan nod semasa kedua-dua senarai terpaut. Lampirkan nod yang lebih kecil pada senarai yang digabungkan dan gerakkan penunjuk senarai itu ke hadapan.
3. Kendalikan Baki Nod: Jika satu senarai kehabisan sebelum yang lain, lampirkan baki nod senarai tidak habis pada senarai yang digabungkan.
4. Kembalikan Senarai Gabungan: Senarai yang digabungkan bermula dari nod di sebelah nod tiruan.

Pelaksanaan Java:

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class LinkedList {

    // Function to merge two sorted linked lists
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // Create a dummy node to act as the starting point
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        // Traverse both lists and compare nodes
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }

        // If one list is exhausted, link the remaining nodes of the other list
        if (l1 != null) {
            current.next = l1;
        } else {
            current.next = l2;
        }

        // The merged list starts from the next node of the dummy node
        return dummy.next;
    }

    // Function to print the linked list
    public void printList(ListNode head) {
        ListNode temp = head;
        while (temp != null) {
            System.out.print(temp.val + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        // Create first sorted linked list: 1 -> 3 -> 5
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(3);
        l1.next.next = new ListNode(5);

        // Create second sorted linked list: 2 -> 4 -> 6
        ListNode l2 = new ListNode(2);
        l2.next = new ListNode(4);
        l2.next.next = new ListNode(6);

        System.out.println("First List:");
        list.printList(l1);

        System.out.println("Second List:");
        list.printList(l2);

        // Merge the two lists
        ListNode mergedList = list.mergeTwoLists(l1, l2);

        System.out.println("Merged List:");
        list.printList(mergedList);
    }
}

Penjelasan:

1. Kelas ListNode:

   • Mewakili setiap nod dalam senarai terpaut dengan nilai integer (val) dan penuding ke nod seterusnya (seterusnya).

2. Kaedah mergeTwoLists:

   • Nod Dummy: Nod tiruan (dummy) digunakan untuk memudahkan proses penggabungan dengan menyediakan titik permulaan.
   • Gelung Perbandingan: Kami merentasi kedua-dua senarai terpaut, membandingkan nod semasa. Nod yang lebih kecil ditambahkan pada senarai yang digabungkan dan kami beralih ke nod seterusnya dalam senarai itu.
   • Baki Nod: Selepas salah satu senarai kehabisan, kami melampirkan baki bahagian senarai yang lain terus ke senarai yang digabungkan.
   • Kembali: Akhirnya, senarai yang digabungkan bermula dari nod bersebelahan dengan nod tiruan.

3. Kaedah printList:

   • Fungsi utiliti ini mencetak semua nod dalam senarai terpaut untuk visualisasi yang mudah.

4. Kaedah utama:

   • Buat dua senarai terpaut diisih: Contohnya, 1 -> 3 -> 5 dan 2 -> 4 -> 6.
   • Gabungkan senarai: Senarai yang digabungkan akan menjadi 1 -> 2 -> 3 -> 4 -> 5 -> 6.
   • Cetak senarai: Sebelum dan selepas bergabung untuk melihat kesannya.

Kerumitan:

• Kerumitan Masa: ( O(n + m) ), dengan ( n ) dan ( m ) ialah panjang dua senarai yang dipautkan. Setiap nod dalam kedua-dua senarai diproses tepat sekali.
• Kerumitan Ruang: ( O(1) ), kerana tiada ruang tambahan digunakan selain daripada beberapa petunjuk.

Kaedah ini mudah dan optimum untuk menggabungkan dua senarai terpaut yang diisih, memastikan kod yang cekap dan bersih.

Atas ialah kandungan terperinci Gabungkan dua senarai terpaut yang diisih dalam cara mudah dan optimum java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!