三种解法

1. 分治
2. 顺序合并
3. 优先队列

首先做这道题，得先会一道基础的题目，没做过的可以先去做
合并两个已排序的链表

分治（归并）

先分而治之，分到不能再分则合并(归并)

图解：

import java.util.*;
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        return merge(lists,0,lists.size()-1);
    }
    public ListNode merge(ArrayList<ListNode> lists, int l, int r){
        // 左右相等说明不能再分
        if(l == r)
            return lists.get(l);
        if(l > r){
            return null;
        }
        int mid = l + (r-l)/2;
        return mergeTwoList(merge(lists,l,mid),merge(lists,mid+1,r));
    }
    //合并两个有序链表
    public ListNode mergeTwoList(ListNode node1, ListNode node2){
        ListNode node = new ListNode(-1);
        ListNode tmp = node;
        while(node1!=null && node2!=null){
            if(node1.val <= node2.val){
                tmp.next = node1;
                node1 = node1.next;
            }else{
                tmp.next = node2;
                node2 = node2.next;
            }
            tmp = tmp.next;
        }
        tmp.next = node1!=null?node1:node2;
        return node.next;
    }
}

遍历合并

图解：

import java.util.*;
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        int n = lists.size();
        if(n == 0)
            return null;
        if(n == 1)
            return lists.get(0);
        ListNode node = lists.get(0);
        for(int i = 1; i < n; i++){
            node = margeTwoList(lists.get(i),node);
        }
        return node;
    }

    public ListNode margeTwoList(ListNode node1, ListNode node2){
        ListNode node = new ListNode(-1);
        ListNode tmp = node;
        while(node1!=null && node2!=null){
            if(node1.val <= node2.val){
                tmp.next = node1;
                node1 = node1.next;
            }else{
                tmp.next = node2;
                node2 = node2.next;
            }
            tmp = tmp.next;
        }
        tmp.next = node1!=null?node1:node2;
        return node.next;
    }
}

使用优先队列

用优先队列建一个小顶堆，每次堆顶为值最小的节点，依次取出，然后再将它的下一个节点放回去。
再重复过程~

public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        //小根堆
        Queue<ListNode> pq = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
        //将全部的节点放进去
        for (ListNode node: lists) {
            if (node != null) {
                pq.offer(node);
            }
        }

        ListNode dummyHead = new ListNode(0);
        ListNode tail = dummyHead;
        while (!pq.isEmpty()) {
            //队首为值最小的节点
            ListNode minNode = pq.poll();
            tail.next = minNode;
            tail = minNode;
            //若拿出来的节点的下一个节点不为null，则再将其放回去
            if (minNode.next != null) {
                pq.offer(minNode.next);
            }
        }

        return dummyHead.next;
    }
}