美文网首页
2019-05-19 Merge k Sorted List

2019-05-19 Merge k Sorted List

作者: 张开翔 | 来源:发表于2019-05-19 23:40 被阅读0次

    question:

    Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
    Input:
    [
    1->4->5,
    1->3->4,
    2->6
    ]
    Output: 1->1->2->3->4->4->5->6

    Ideas:

    //链表
       public static ListNode mergeKLists(ListNode[] lists){
            if(lists==null || lists.length<1)
                return null;
            ListNode head = new ListNode(-1);
            ListNode phead =head;
            int count=0,index=0,min;    //奇数已经遍历完的链表
            while(count<lists.length){
                //找出K个链表的头结点值最小的那一个
                count=0;
                min = Integer.MAX_VALUE;
                for(int i=0;i<lists.length;i++){
                    if(lists[i]==null){
                        count++;
                        continue;
                    }
                    if(lists[i].val<min){
                        min = lists[i].val;
                        index=i;
                    }
                }
                if(count==lists.length)
                    break;
                phead.next=lists[index];
                phead=phead.next;
                lists[index]=lists[index].next;
            }
            return head.next;
        }
    

    方案二

    //优先队列
      public static ListNode mergeKLists2(ListNode[] lists){
    
            ListNode head = new ListNode(-1);
            ListNode phead = head;
            //构造优先队列
            Queue<ListNode> minheap = new PriorityQueue<ListNode>(new Comparator<ListNode>() {
                @Override
                public int compare(ListNode o1, ListNode o2) {
                    if(o1.val<o2.val)
                        return -1;
                    else if(o1.val==o2.val)
                        return 0;
                    else {
                        return 1;
                    }
                }
            }); //初始化优先队列
            for(ListNode l:lists){
                if(l!=null)
                    minheap.add(l);
            }
            while(!minheap.isEmpty()){
                phead.next=minheap.poll();  //队列的头元素必为所有链表头元素中的最小值
                phead=phead.next;
                if(phead.next!=null)
                    minheap.add(phead.next);
            }
            return head.next;
        }
    

    方案三

    //归并类似
        public static ListNode mergeKLists3(ListNode[] lists){
    
            int length=lists.length;
            int inteval=1;
            while(inteval<length){
                for(int i=0;i<length-inteval;i+=inteval*2){
                    lists[i] = mergeTwoLists(lists[i],lists[i+inteval]);
                }
                inteval *=2;
            }
            return lists[0];
        }
    
    
    

    相关文章

      网友评论

          本文标题:2019-05-19 Merge k Sorted List

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