本文共 2974 字，大约阅读时间需要 9 分钟。

题目描述

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]

输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6 示例 2：

输入：lists = []

输出：[] 示例 3：

输入：lists = [[]]

输出：[]

提示：

k == lists.length

0 <= k <= 10^4 0 <= lists[i].length <= 500 -10^4 <= lists[i][j] <= 10^4 lists[i] 按 升序 排列 lists[i].length 的总和不超过 10^4

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/merge-k-sorted-lists 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

C++

方法一：分治法

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode() {} *     ListNode(int val) { this.val = val; } *     ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ /* 思路一：分治法 */class Solution {
       public ListNode mergeKLists(ListNode[] lists){
           if(lists.length == 0)            return null;        if(lists.length == 1)            return lists[0];        if(lists.length == 2){
              return mergeTwoLists(lists[0],lists[1]);        }        int mid = lists.length/2;        ListNode[] l1 = new ListNode[mid];        for(int i = 0; i < mid; i++){
               l1[i] = lists[i];        }        ListNode[] l2 = new ListNode[lists.length-mid];        for(int i = mid,j=0; i < lists.length; i++,j++){
               l2[j] = lists[i];        }        return mergeTwoLists(mergeKLists(l1),mergeKLists(l2));    }    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
           if (l1 == null) return l2;        if (l2 == null) return l1;        ListNode head = null;        if (l1.val <= l2.val){
               head = l1;            head.next = mergeTwoLists(l1.next, l2);        } else {
               head = l2;            head.next = mergeTwoLists(l1, l2.next);        }        return head;    }}

JAVA

优先队列法

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode() {} *     ListNode(int val) { this.val = val; } *     ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ /* 思路二：最小堆优先队列 用容量为K的最小堆优先队列，把链表的头结点都放进去，然后出队当前优先队列中最小的，挂上链表，，然后让出队的那个节点的下一个入队，再出队当前优先队列中最小的，直到优先队列为空。 */class Solution {
       public ListNode mergeKLists(ListNode[] lists){
        if(lists.length==0){
            return null;     }     ListNode prehead=new ListNode(0); //     ListNode  pre=prehead;  //游标     PriorityQueue
   
     pq=new PriorityQueue<>(new Comparator
    
     (){
            @Override         public int  compare(ListNode o1,ListNode o2){
                return o1.val-o2.val;         }     });     for(ListNode list:lists){
            if(list==null){
                continue;         }         pq.add(list);     }     while(!pq.isEmpty()){
            ListNode nextNode=pq.poll();         pre.next=nextNode;         pre=pre.next;         if(nextNode.next!=null){
                pq.add(nextNode.next);         }              }        return  prehead.next;    } }