NC51：合并k个已排序的链表

解法1：优先级队列
优先级队列：小根堆

    PriorityQueue<Integer> queue=new PriorityQueue<>(new Comparator<Integer>(){
        public int compare(Integer a,Integer b){
            return a.compareTo(b);
        }
    });
//  PriorityQueue<Integer> queue = new PriorityQueue();

最小k个数：大根堆
PriorityQueue<Integer> maxHeap=new PriorityQueue<Integer>(k,new Comparator<Integer>(){
        @Override
        public int compare(Integer o1,Integer o2){
                return o2.compareTo(o1);
            }
        });
PriorityQueue<Integer> maxHeap=new PriorityQueue<Integer>(k,(a,b)->b.compareTo(a));     

代码：

import java.util.PriorityQueue;
import java.util.ArrayList;
import java.util.Comparator;
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if(lists == null || lists.size() < 0){
           return null;
       }
        PriorityQueue<Integer> queue=new PriorityQueue<>(new Comparator<Integer>(){
            public int compare(Integer a,Integer b){
                return a.compareTo(b);
            }
        });
//         PriorityQueue<Integer> queue = new PriorityQueue();
        for(ListNode node : lists){
            while(node != null){
                queue.add(node.val);
                node = node.next;
            }
        }
        ListNode res = new ListNode(0);
        ListNode tmp= res;
        while(!queue.isEmpty()){
            ListNode temp = new ListNode(queue.poll());
            tmp.next = temp;
            tmp = tmp.next;
        }
        return res.next;
    }
}

解法2：递归
如果表1当前值小于表2当前值，表1当前值成为新链表的表头，否则返回表2的当前值作为新链表的表头。 比较当前链表的值，较小的取其子链表继续递归。
当有一个链表取到子链表为空时，说明已经比较完成，可以直接返回非空的链表，返回值赋给了l1.next或者l2.next，但无论如何，最终还是沿着递归链不断返回，最终返回的是新有序链表的表头。

    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        ListNode result=null;
        for(ListNode list : lists){
            result=MergeList(result,list);
        }
        return result;
    }
    public ListNode MergeList(ListNode list1,ListNode list2){
        if(list1==null){
            return list2;
        }
        if(list2==null){
            return list1;
        }

        ListNode newHead=null;
        if(list1.val>list2.val){
            newHead=list2;
            list2.next=MergeList(list1,list2.next);
        }
        else{
            newHead=list1;
            list1.next=MergeList(list1.next,list2);
        }
        return newHead;
    }

解法3：递归+归并排序的思路

public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if(lists == null || lists.length == 0){
            return null;
        }
        return mergeList(lists, 0, lists.length - 1);
    }

    public ListNode mergeList(ListNode[] lists, int left, int right){
        if(left >= right)
            return lists[left];
        int mid = left + (right - left) / 2;
        ListNode l1 = mergeList(lists, left, mid);
        ListNode l2 = mergeList(lists, mid + 1, right);
        return merge(l1, l2);
    }

    public ListNode merge(ListNode l1, ListNode l2){
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        ListNode ans = new ListNode(0);
        ListNode p = ans;
        while(l1 != null && l2 != null){
            if(l1.val <= l2.val){
                p.next = l1;
                l1 = l1.next;
            }
            else{
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        p.next = l1 == null? l2 : l1;
        return ans.next;
    }

解法4：循环遍历
思路： 已经解决了两个排序链表的问题，则k个链表的排序也进行依次遍历即可解决；
因为两个链表合并的时间复杂度是O(n)，空间复杂度是O(1)；
k个链表是外加一次循环，所以时间复杂度为O（n*m）
（n为lists数组的长度，m为数组中链表的长度），空间复杂度为O（1）

    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        ListNode result=null;
        for(ListNode list : lists){
            result=MergeList(result,list);
        }
        return result;
    }
    public ListNode MergeList(ListNode l1,ListNode l2){
        ListNode tmp = new ListNode(-1);
        ListNode cur = tmp;
        while(l1 != null && l2 != null) {
            if(l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            }
            else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        if(l1 == null) cur.next = l2; 
        // l1遍历为空 那么l2还有节点呢，所以指向l2的节点。

        if(l2 == null) cur.next = l1; 
        // l2遍历为空 那么l1还有节点呢，所以指向l1的节点。

        return tmp.next;
    }