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中有序链表的合并操作，并在实际编程中灵活运用。