合并K个已排序的链表

知识回顾：

合并两个有序的链表

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;
    }

解法一：遍历法

第一次从中取出两个链表合并，然后再依次取出一个链表进行合并

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;
    }
}

缺点

时间复杂度为 O(kN)

优化

分治： O(logkN)

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) {
        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;
            if (minNode.next != null) {
                pq.offer(minNode.next);
            }
        }
        return dummyHead.next;
    }
}