Java实现合并多个升序链表

下面是Java实现合并多个升序链表的完整攻略：

问题分析

要合并多个升序链表，首先需要明确链表是如何存储的。链表的每个节点包含两个元素，一个是该节点的值，另一个是下一个节点的指针。因此，对于多个升序链表，只需要依次比较每个链表的第一个节点的值，选出最小值，然后定义一个新的链表存储这个最小值，同时更新选出最小值的链表的头节点，继续比较下一个节点，选出最小值，直到所有节点都被合并到新的链表中。因为新的链表的节点值始终是升序的，所以无需再排序。

代码实现

在Java中，可以使用链表来表示节点。具体实现过程如下：

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        if (lists.length == 1) {
            return lists[0];
        }
        ListNode head = new ListNode(0);
        ListNode p = head;
        PriorityQueue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });
        for (ListNode node : lists) {
            if (node != null) {
                queue.offer(node);
            }
        }
        while (!queue.isEmpty()) {
            ListNode node = queue.poll();
            p.next = node;
            p = p.next;
            if (node.next != null) {
                queue.offer(node.next);
            }
        }
        return head.next;
    }
}

首先判断链表数组是否为空，如果为空则直接返回null；
如果链表数组只有一个元素，则直接返回该元素；
遍历链表数组，将所有第一个节点不为空的链表放入一个小根堆中（PriorityQueue），按照节点的值进行比较；
定义一个新的链表头节点head，以及一个指向head的指针p；
从小根堆中取出最小的节点，将其接入新的链表中，并更新p指针；
如果该节点的next不为空，则将其next放入小根堆中；
重复步骤5和步骤6，直到小根堆为空；
返回新的链表头的next节点。

示例说明

假设有下列三个升序链表：

l1: 1->3->5
l2: 2->4->6
l3: 0->7->8

则将这三个链表合并后的结果为：

0->1->2->3->4->5->6->7->8

示例代码：

ListNode l1 = new ListNode(1);
l1.next = new ListNode(3);
l1.next.next = new ListNode(5);

ListNode l2 = new ListNode(2);
l2.next = new ListNode(4);
l2.next.next = new ListNode(6);

ListNode l3 = new ListNode(0);
l3.next = new ListNode(7);
l3.next.next = new ListNode(8);

ListNode[] lists = new ListNode[] {l1, l2, l3};

Solution solution = new Solution();
ListNode result = solution.mergeKLists(lists);

while(result != null) {
    System.out.print(result.val + " ");
    result = result.next;
}

输出结果为：

0 1 2 3 4 5 6 7 8

另外一个示例：

l1: 3->8->10
l2: 1->2->3->7
l3: 4->6