【数据结构】算法 合并K个有序链表Merge k Sorted Lists

目录

• 合并K个有序链表Merge k Sorted Lists
  • 思路
• Tag

合并K个有序链表Merge k Sorted Lists

有一个链表数组，每个链表都是有序的【升序排列】。合并所有链表到一个升序链表中。

思路

N路有序链表合并，借助优先队列，维持一个容量为N的队列，每次出队最小的，然后再入队一个元素。

public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length==0){
            return null;
        }
        ListNode h = new ListNode(0);
        ListNode p = h;

        PriorityQueue<ListNode> pq = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
        for (ListNode x : lists) {
           if (x!=null){
               pq.offer(x);
           }
        }

        while (!pq.isEmpty()){
            ListNode cur = pq.peek();
            p.next = cur;
            pq.poll();
            p = cur;
            if (cur.next!=null){
                pq.offer(cur.next);
            }
        }
        return h.next;
    }

Tag

heap linkedlist