[Leetcode] Merge k Sorted Lists

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

Solution 1:

PriorityQueue:

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) {
 7  *         val = x;
 8  *         next = null;
 9  *     }
10  * }
11  */
12 public class Solution {
13     class myComparator implements Comparator<ListNode> {
14 
15         @Override
16         public int compare(ListNode o1, ListNode o2) {
17             // TODO Auto-generated method stub
18             if (o1.val < o2.val) {
19                 return -1;
20             } else if (o1.val > o2.val) {
21                 return 1;
22             }
23             return 0;
24         }
25     }
26 
27     public ListNode mergeKLists(List<ListNode> lists) {
28         if(lists==null||lists.size()==0)
29             return null;
30         PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(lists.size(),
31                 new myComparator());
32         for (ListNode head : lists) {
33             if (head != null) {
34                 pq.add(head);
35             }
36         }
37         ListNode dummy = new ListNode(-1);
38         ListNode cur = dummy;
39         while (!pq.isEmpty()) {
40             ListNode temp=pq.peek();
41             pq.poll();
42             cur.next=temp;
43             cur=cur.next;
44             if(temp.next!=null){
45                 pq.add(temp.next);
46             }
47         }
48         return dummy.next;
49     }
50 }

Solution 2:

MergeSort

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) {
 7  *         val = x;
 8  *         next = null;
 9  *     }
10  * }
11  */
12 public class Solution {
13     public ListNode mergeKLists(List<ListNode> lists) {
14         if(lists==null||lists.size()==0)
15             return null;
16         
17         return mSort(lists,0,lists.size()-1);
18     }
19 
20     private ListNode mSort(List<ListNode> lists, int start, int end) {
21         // TODO Auto-generated method stub
22         if(start<end){
23             int mid=(start+end)/2;
24             ListNode left=mSort(lists, start, mid);
25             ListNode right=mSort(lists, mid+1, end);
26             return merge(left,right);
27         }
28         return lists.get(start);
29     }
30 
31     private ListNode merge(ListNode left, ListNode right) {
32         // TODO Auto-generated method stub
33         if(left==null)
34             return right;
35         if(right==null)
36             return left;
37         ListNode dummy=new ListNode(-1);
38         ListNode cur=dummy;
39         while(left!=null&&right!=null){
40             if(left.val<right.val){
41                 cur.next=left;
42                 left=left.next;
43                 cur=cur.next;
44             }else{
45                 cur.next=right;
46                 right=right.next;
47                 cur=cur.next;
48             }
49         }
50         if(left!=null){
51             cur.next=left;
52         }
53         if(right!=null){
54             cur.next=right;
55         }
56         return dummy.next;
57     }
58 }