美文网首页
23. 合并K个排序链表

23. 合并K个排序链表

作者: 编程小王子AAA | 来源:发表于2020-06-07 18:50 被阅读0次

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

    示例:

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


    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            ListNode fakeHead=new ListNode(0);
            ListNode p=fakeHead;
            int k=lists.length;
            PriorityQueue<ListNode> heap=new PriorityQueue<>((a,b)->(a.val-b.val));
            for(int i=0;i<k;i++){
                if(lists[i]!=null){
                    heap.offer(lists[i]);
                }
            }
            while(!heap.isEmpty()){
                ListNode node=heap.poll();
                p.next=node;
                p=p.next;
                if(node.next!=null){
                    heap.offer(node.next);
                }
            }
            return fakeHead.next;
        }
    }
    

    相关文章

      网友评论

          本文标题:23. 合并K个排序链表

          本文链接:https://www.haomeiwen.com/subject/thtnzhtx.html