Merge k Sorted Lists(合并k个有序链表)leetcode23

不念不忘少年蓝@ 2022-05-23 01:58 191阅读 0赞

Merge *k* sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
    [
      1->4->5,
      1->3->4,
      2->6
    ]
    Output: 1->1->2->3->4->4->5->6

code1：（暴力破解）

public ListNode mergeKLists(ListNode[] lists) {
            if(lists==null||lists.length<=0)
                return null;
            if(lists.length==1)
                return lists[0];
            ListNode head=new ListNode(-1);
            ListNode result=head;
            int empty=0;
            int j;
                while(empty!=lists.length){
                    empty=0;
                    int minV=Integer.MAX_VALUE;
                    int minI=-1;
                    for(j=0;j<lists.length;j++){                 
                    ListNode node=lists[j];
                        if(node==null){
                            empty++;
                            continue;
                            
                        }
                        if(node.val<minV){
                            minV=node.val;
                            minI=j;
                        }       
                    }
                    if(minI!=-1){
                        //System.out.println(minI);
                        head.next=lists[minI];
                        head=head.next;
                        lists[minI]=lists[minI].next;
                    } 
                }
            return result.next;
            
        }

code2：（大优化）

public ListNode mergeKLists(ListNode[] lists) {
            if(lists.length==0)
                return null;
            return merge(0,lists.length-1,lists);
        }
        public ListNode merge(int i,int j,ListNode[] lists) {
            if(j<i)return null;
            if(i==j)return lists[i];
            int mid=i+(j-i)/2;
            ListNode l=merge(i,mid,lists);
            ListNode r= merge(mid+1,j,lists);
            ListNode dummy =new ListNode(0);
            ListNode runner= dummy;
    
            while(l!=null && r!=null) {
                if(l.val>r.val) {
                    runner.next=r;
                    r=r.next;
                    runner=runner.next;
                }
                else {
                    runner.next=l;
                    l=l.next;
                    runner=runner.next;
                }
            }
            if(l==null && r==null)
                return dummy.next;
            if(l==null)
                runner.next=r;
            else
                runner.next=l;
            return dummy.next;
        }