23.合并K个排序链表

题目描述

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

题解

K指针

参考21题合并两个有序链表的题目, 思路就是查看当前K个链表的头结点值的大小, 挑选出最小的节点, 把它接在cur后面

public ListNode mergeKLists(ListNode[] lists) {
    ListNode dummy = new ListNode(0);
    ListNode cur = dummy;
    int k = lists.length;

    while (true){
        int minIndex = -1;
        ListNode minNode = null;

        for (int i = 0; i < k; i++) {
            if (lists[i]==null)
                continue;

            if (minNode==null||lists[i].val<minNode.val){
                minNode = lists[i];
                minIndex = i;
            }

        }
        if (minIndex == -1)
            break;

        cur.next = minNode;
        cur = cur.next;
        lists[minIndex] = lists[minIndex].next;


    }
    return dummy.next;
}

小根堆

利用堆的结构, 先将K个头结点放入堆中, 那么堆顶的节点必定是最小的节点, 将其接在cur节点之后. 将弹出节点的next节点继续放入堆中, 使堆有进有出并且保证堆顶的节点一直是最小的.

public ListNode mergeKLists(ListNode[] lists) {
    Queue<ListNode> queue = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
    for (ListNode listNode : lists) {
        if (listNode != null)
            queue.offer(listNode);
    }

    ListNode dummy = new ListNode(0);
    ListNode cur = dummy;

    while (!queue.isEmpty()) {
        ListNode minNode = queue.poll();
        cur.next = minNode;
        cur = cur.next;
        if (minNode.next!=null)
            queue.offer(minNode.next);

    }

    return dummy.next;
}