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

对于这道题，之前并不知道java中有一个封装好的数据结构--优先队列。优先队列其实相当于一个最大或最小堆，能够根据所规定的的实现方法来对队列中的元素进行排序。

这样就好办了，把要排序的元素放在队列中，每次取出最小的那个，并把这个元素从原来的列表中删除 ，之后将原来的列表的新的最新的头元素节点重新放入队列中，如果为null，就跳过

1 package Merge.k.Sorted.Lists; 2  3 import java.util.ArrayList; 4 import java.util.Comparator; 5 import java.util.List; 6 import java.util.PriorityQueue; 7 import java.util.function.Function; 8 import java.util.function.ToDoubleFunction; 9 import java.util.function.ToIntFunction;10 import java.util.function.ToLongFunction;11 12 public class MergekSortedLists1 {13     public ListNode mergeKLists(List
     
       lists) {14         if(lists==null||lists.size()==0) return null;15         int size=lists.size();16         PriorityQueue 
      
       queue=new PriorityQueue
       
        (size,new Comparator
        
         (){17             public int compare(ListNode o1, ListNode o2) {18                 return o1.val-o2.val;19             }    20         });21         for(ListNode head:lists){22             if(head!=null)23             queue.offer(head);24         }25         ListNode head=null;26         ListNode index=null;27         while(!queue.isEmpty()){28             ListNode min=queue.poll();29             if(head==null){30                 head=min;31                 index=min;32                 33             }else{34                 index.next=min;35                 index=index.next;36             }37             ListNode curr=min;38             curr=curr.next;39             if(curr!=null)40             queue.offer(curr);41         }42         return head;        43     }44     public static void main(String args[]){45         MergekSortedLists1 service=new MergekSortedLists1();46         List
         
           lists=new ArrayList
          
           ();47 ListNode n1=new ListNode(1);48 ListNode n2=new ListNode(2);49 ListNode n3=new ListNode(2);50 n1.next=n2;51 n2.next=n3;52 ListNode x1=new ListNode(1);53 ListNode x2=new ListNode(1);54 ListNode x3=new ListNode(2);55 x1.next=x2;56 x2.next=x3;57 lists.add(n1);58 lists.add(x1);59 ListNode head=service.mergeKLists(lists);60 while(head!=null){61 System.out.println(head.val);62 head=head.next;63 }64 }65 66 }