# 0023. Merge k Sorted Lists
###### tags: `Leetcode` `FaceBook` `Hard` `Priority Queue` `Merge Sorted List`
Link: https://leetcode.com/problems/merge-k-sorted-lists/
## 思路
### 思路一 Priority Queue O(Nlogk) O(k) N是node总个数 k是linkedlist个数
### 思路二 Divide and Conquer (Recursive) O(Nlogk) O(logk)
### 思路三 Divide and Conquer (Iterative) O(Nlogk) O(1)
时间复杂度分析：

## Code
### 思路一

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length==0) return null;
        ListNode dummyNode = new ListNode();
        ListNode tail = dummyNode;
        Queue<ListNode> q = new PriorityQueue<>((a,b)->(a.val-b.val));
        
        for(ListNode node:lists){
            if(node!=null) q.add(node);
        }
        while(!q.isEmpty()){
            tail.next = q.poll();
            tail = tail.next;
            if(tail.next!=null) q.add(tail.next);
        }
        return dummyNode.next;
    }
}

### 思路二

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummyNode = new ListNode();
        ListNode prev = dummyNode;
        while(l1!=null && l2!=null){
            if(l1.val<l2.val){
                prev.next = l1;
                prev = l1;
                l1 = l1.next;
            }
            else{
                prev.next = l2;
                prev = l2;
                l2 = l2.next;
            }
        }
        if(l2 != null){
            prev.next = l2;
        }
        else{
            prev.next = l1;
        }
        return dummyNode.next;
    }
    
    public ListNode mergeKLists(ListNode[] lists){
        return mergeKLists(Arrays.asList(lists));
    }
    
    public ListNode mergeKLists(List<ListNode> lists) {
        if (lists.size()==0) return null;
        if (lists.size()==1) return lists.get(0);
        if (lists.size()==2) return mergeTwoLists(lists.get(0), lists.get(1));
        return mergeTwoLists(mergeKLists(lists.subList(0, lists.size()/2)), 
            mergeKLists(lists.subList(lists.size()/2, lists.size())));
    }
}

### 思路三

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int len = lists.length;
        int interval = 1;
        while(interval<len){
            for(int i = 0;i < len-interval;i+=interval*2){
                lists[i] = merge2Lists(lists[i],lists[i+interval]);
            }
            interval*=2;
        }
        return len>0?lists[0]:null;
    }
    public ListNode merge2Lists(ListNode l1, ListNode l2) {
        ListNode dummyNode = new ListNode();
        ListNode prev = dummyNode;
        while(l1!=null && l2!=null){
            if(l1.val<l2.val){
                prev.next = l1;
                prev = l1;
                l1 = l1.next;
            }
            else{
                prev.next = l2;
                prev = l2;
                l2 = l2.next;
            }
        }
        if(l2 != null){
            prev.next = l2;
        }
        else{
            prev.next = l1;
        }
        return dummyNode.next;
    }
}