Java有序鏈表如何合并

Java有序鏈表如何合并

在Java編程中，鏈表是一種常見的數據結構，它由一系列節點組成，每個節點包含數據和指向下一個節點的指針。有序鏈表是指鏈表中的節點按照某種順序（如升序或降序）排列。合并兩個有序鏈表是一個常見的操作，通常用于合并兩個已排序的鏈表，生成一個新的有序鏈表。

本文將詳細介紹如何在Java中合并兩個有序鏈表，包括鏈表的定義、合并算法的實現以及相關的代碼示例。

1. 鏈表的定義

在Java中，鏈表通常通過定義一個Node類來表示。每個Node對象包含兩個部分：數據域和指針域。數據域用于存儲節點的值，指針域用于指向下一個節點。

class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

2. 合并兩個有序鏈表的算法

合并兩個有序鏈表的基本思路是：創建一個新的鏈表，然后依次比較兩個鏈表的節點，將較小的節點添加到新鏈表中，直到其中一個鏈表為空。最后，將另一個鏈表中剩余的節點直接添加到新鏈表的末尾。

2.1 算法步驟

1. 初始化：創建一個新的鏈表頭節點dummy，并定義一個指針current指向dummy。
2. 比較節點：比較兩個鏈表的當前節點，將較小的節點添加到current的后面，并將current指針移動到新添加的節點。
3. 移動指針：將較小節點所在鏈表的指針向后移動一位。
4. 重復步驟2和3：直到其中一個鏈表的指針為空。
5. 處理剩余節點：將另一個鏈表中剩余的節點直接添加到current的后面。
6. 返回結果：返回dummy.next，即新鏈表的頭節點。

2.2 代碼實現

public class MergeSortedLinkedLists {

    public static Node mergeTwoLists(Node l1, Node l2) {
        // 創建一個虛擬頭節點
        Node dummy = new Node(0);
        Node current = dummy;

        // 遍歷兩個鏈表
        while (l1 != null && l2 != null) {
            if (l1.data <= l2.data) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }

        // 處理剩余的節點
        if (l1 != null) {
            current.next = l1;
        } else {
            current.next = l2;
        }

        // 返回合并后的鏈表頭節點
        return dummy.next;
    }

    public static void printList(Node head) {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // 創建第一個有序鏈表 1 -> 3 -> 5
        Node l1 = new Node(1);
        l1.next = new Node(3);
        l1.next.next = new Node(5);

        // 創建第二個有序鏈表 2 -> 4 -> 6
        Node l2 = new Node(2);
        l2.next = new Node(4);
        l2.next.next = new Node(6);

        // 合并兩個有序鏈表
        Node mergedList = mergeTwoLists(l1, l2);

        // 打印合并后的鏈表
        printList(mergedList);  // 輸出: 1 2 3 4 5 6
    }
}

2.3 代碼解析

• 虛擬頭節點：dummy節點用于簡化代碼，避免處理空鏈表的情況。current指針始終指向新鏈表的最后一個節點。
• 比較節點：通過比較l1和l2的當前節點，將較小的節點添加到新鏈表中。
• 處理剩余節點：當其中一個鏈表遍歷完畢后，直接將另一個鏈表的剩余部分添加到新鏈表中。
• 返回結果：最終返回dummy.next，即新鏈表的頭節點。

3. 時間復雜度分析

合并兩個有序鏈表的時間復雜度為O(n + m)，其中n和m分別是兩個鏈表的長度。因為我們需要遍歷兩個鏈表的所有節點。

空間復雜度為O(1)，因為我們只使用了常數個額外的指針變量。

4. 擴展：合并K個有序鏈表

在實際應用中，可能會遇到需要合并K個有序鏈表的情況。合并K個有序鏈表可以通過分治法或優先隊列（最小堆）來實現。

4.1 分治法

分治法的基本思路是將K個鏈表分成兩部分，分別合并這兩部分，然后再將結果合并。

public static Node mergeKLists(Node[] lists) {
    if (lists == null || lists.length == 0) {
        return null;
    }
    return mergeKLists(lists, 0, lists.length - 1);
}

private static Node mergeKLists(Node[] lists, int left, int right) {
    if (left == right) {
        return lists[left];
    }
    int mid = left + (right - left) / 2;
    Node l1 = mergeKLists(lists, left, mid);
    Node l2 = mergeKLists(lists, mid + 1, right);
    return mergeTwoLists(l1, l2);
}

4.2 優先隊列（最小堆）

優先隊列的基本思路是將所有鏈表的頭節點放入最小堆中，每次從堆中取出最小的節點，并將其下一個節點放入堆中，直到堆為空。

public static Node mergeKLists(Node[] lists) {
    if (lists == null || lists.length == 0) {
        return null;
    }

    PriorityQueue<Node> minHeap = new PriorityQueue<>((a, b) -> a.data - b.data);

    // 將所有鏈表的頭節點放入最小堆
    for (Node list : lists) {
        if (list != null) {
            minHeap.offer(list);
        }
    }

    Node dummy = new Node(0);
    Node current = dummy;

    // 從最小堆中取出最小的節點，并將其下一個節點放入堆中
    while (!minHeap.isEmpty()) {
        Node minNode = minHeap.poll();
        current.next = minNode;
        current = current.next;

        if (minNode.next != null) {
            minHeap.offer(minNode.next);
        }
    }

    return dummy.next;
}

5. 總結

合并有序鏈表是鏈表操作中的一個常見問題，掌握其基本算法對于理解鏈表的結構和操作非常重要。本文詳細介紹了如何在Java中合并兩個有序鏈表，并提供了代碼示例和擴展內容。通過分治法或優先隊列，我們還可以進一步解決合并K個有序鏈表的問題。

希望本文能幫助你更好地理解Java中有序鏈表的合并操作，并在實際編程中靈活運用。