用java簡單且最佳的方式合併兩個排序的鍊錶

合併兩個排序鍊錶是一個可以有效解決的常見問題。以下是如何使用 Java 以簡單且最佳的方式完成此操作。

步驟：

1. 建立虛擬節點：使用虛擬節點來幫助簡化合併過程。該節點將作為合併清單的開始。
2. 比較節點：比較兩個鍊錶的目前節點。將較小的節點附加到合併列表並將該列表的指標向前移動。
3. 處理剩餘節點：如果一個清單先於另一個清單耗盡，則將未耗盡清單的剩餘節點附加到合併清單。
4. 傳回合併清單：合併清單從虛擬節點旁的節點開始。

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);
    }
}

解釋：

1. ListNode 類別:

   • 用一個整數值（val）和一個指向下一個節點（next）的指標來表示鍊錶中的每個節點。

2. mergeTwoLists 方法:

   • 虛擬節點：虛擬節點（dummy）用於透過提供起點來簡化合併過程。
   • 比較循環：我們遍歷兩個鍊錶，比較目前節點。較小的節點將添加到合併列表中，然後我們移動到該列表中的下一個節點。
   • 剩餘節點：其中一個清單耗儘後，我們將另一個清單的剩餘部分直接附加到合併清單。
   • 回傳：最後，合併清單從虛擬節點旁的節點開始。

3. printList 方法:

   • 此實用函數會列印連結清單中的所有節點，以便於視覺化。

4. 主要方法:

   • 建立兩個排序鍊錶：例如1 -> 3-> 5和2-> 4-> 6.
   • 合併清單：合併後的清單將為 1 -> 2-> 3-> 4-> 5-> 6.
   • 列印清單：合併前後查看效果。

複雜：

• 時間複雜度： ( O(n + m) )，其中 ( n ) 和 ( m ) 是兩個鍊錶的長度。兩個清單中的每個節點都只處理一次。
• 空間複雜度：( O(1) )，因為除了幾個指標之外沒有使用額外的空間。

此方法既簡單又適合合併兩個排序的鍊錶，確保程式碼有效率且乾淨。

以上是用java簡單且最佳的方式合併兩個排序的鍊錶的詳細內容。更多資訊請關注PHP中文網其他相關文章！