题意

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

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

示例

输入：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

思路

1. 优先级队列 时间复杂度：O(n∗log(k))O(n*log(k))O(n∗log(k))，n 是所有链表中元素的总和，k 是链表个数。
2. 分而治之 链表两两合并

代码

• cpp

优先级队列

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*,vector<ListNode*>,function<bool(ListNode*, ListNode*)>> heap([](ListNode* L1,ListNode* L2){
            return L1->val >= L2->val;
        });

        ListNode* res = new ListNode;
        ListNode* tail = res;
        for(auto i : lists){
            if(i != nullptr){
                heap.push(i);
            }
        } 

        while(!heap.empty()){
            tail->next = heap.top();
            heap.pop();
            tail = tail->next;
            if(tail->next)
                heap.push(tail->next);
        }

        return res->next;
    }
};

分而治之

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size() == 0)
            return nullptr;
        return merge(0,lists.size()-1,lists);
    }

    ListNode* merge(int left,int right,vector<ListNode*>& lists){
        if(left >= right)
            return lists[left];
        int mid = (left+right) / 2;
        ListNode* leftNode = merge(left,mid,lists);
        ListNode* rightNode = merge(mid+1,right,lists);
        return dfs(leftNode,rightNode);
    }

    ListNode* dfs(ListNode* left,ListNode* right){
        if(left == nullptr)
            return right;
        if(right == nullptr)
            return left;
        if(left->val < right->val){
            left->next = dfs(left->next,right);
            return left;
        }
        else{
            right->next = dfs(left,right->next);
            return right;
        }
    }
};

• 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; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0)
            return null;
        PriorityQueue<ListNode> heap = new PriorityQueue<>((L1,L2) -> L1.val - L2.val);

        ListNode res = new ListNode();
        ListNode tail = res;
        for(ListNode i : lists){
            if(i != null){
                heap.add(i);
            }
        } 

        while(heap.isEmpty() == false){
            tail.next = heap.poll();
            tail = tail.next;
            if(tail.next != null)
                heap.add(tail.next);
        }

        return res.next;
    }
}

分而治之

/**
 * 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;
        return merge(0,lists.length-1,lists);
    }

    ListNode merge(int left,int right,ListNode[] lists){
        if(left >= right)
            return lists[left];
        int mid = (left+right) / 2;
        ListNode leftNode = merge(left,mid,lists);
        ListNode rightNode = merge(mid+1,right,lists);
        return dfs(leftNode,rightNode);
    }

    ListNode dfs(ListNode left,ListNode right){
        if(left == null)
            return right;
        if(right == null)
            return left;
        if(left.val < right.val){
            left.next = dfs(left.next,right);
            return left;
        }
        else{
            right.next = dfs(left,right.next);
            return right;
        }
    }
}