[LeetCode] Merge k Sorted Lists (Java)

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Analysis

At first I thought this problem was quite easy. We can just pick the smallest one from all heads of lists and then connect it to the final list. But the complexity of this algorithm will be O(n²k), in which n is the number of lists and k is the average number of nodes in one list. However, my code passed the OJ at that time. This algorithm can be TLE easily, so it needs to be improved.

There are two ways to do this.

The first one is the recursive version. It’s similar to merge sort. For example, assuming we have 4 lists: 1, 2, 3, 4. We can merge 1 and 2 to be a new list 5. And 3 and 4 can be merged to be a new list 6. Finally we merge 5 and 6 to get the result. So in this algorithm, we divide the lists by 2 until its size reaches 1. And then merge them from bottom to top.

The second one is to use a priority queue. We can add the heads of all lists in to the queue. And we can poll out the smallest one. If the next node of this smallest node is not null, we can add the next node to the queue. We will continue doing this until the queue is empty.

Code

Recursive version

public class Solution {
    public ListNode mergeKLists(List<ListNode> lists) {
        if (lists.size() == 0)
            return null;
        return mergeKLists(lists, 0, lists.size() - 1);
    }
    
    public ListNode mergeKLists(List<ListNode> lists, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            return merge(mergeKLists(lists, left, mid), mergeKLists(lists, mid + 1, right));
        }
        return lists.get(left);
    }
    
    public ListNode merge(ListNode m, ListNode n) {
        ListNode head = new ListNode(0);
        ListNode p = head;
        while (m != null && n != null) {
            if (m.val < n.val) {
                p.next = m;
                p = p.next;
                m = m.next;
            } else {
                p.next = n;
                p = p.next;
                n = n.next;
            }
        }
        if (m != null)
            p.next = m;
        else
            p.next = n;
        return head.next;
    }
}

public class Solution {

public ListNode mergeKLists(List<ListNode> lists) {

if (lists.size() == 0)

return null;

return mergeKLists(lists, 0, lists.size() - 1);

}

public ListNode mergeKLists(List<ListNode> lists, int left, int right) {

if (left < right) {

int mid = (left + right) / 2;

return merge(mergeKLists(lists, left, mid), mergeKLists(lists, mid + 1, right));

}

return lists.get(left);

}

public ListNode merge(ListNode m, ListNode n) {

ListNode head = new ListNode(0);

ListNode p = head;

while (m != null && n != null) {

if (m.val < n.val) {

p.next = m;

p = p.next;

m = m.next;

} else {

p.next = n;

p = p.next;

n = n.next;

}

if (m != null)

p.next = m;

else

p.next = n;

return head.next;

}

Priority queue version

public class Solution {
    public ListNode mergeKLists(List<ListNode> lists) {
        if (lists.size() == 0)
            return null;
        PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.size(), new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });
        for (int i = 0; i < lists.size(); i++) {
            if (lists.get(i) != null)
                queue.add(lists.get(i));
        }

        ListNode head = new ListNode(0);
        ListNode p = head;
        while (!queue.isEmpty()) {
            ListNode node = queue.poll();
            p.next = node;
            if (node.next != null)
                queue.add(node.next);
            p = p.next;
        }
        return head.next;
    }
}

public class Solution {

public ListNode mergeKLists(List<ListNode> lists) {

if (lists.size() == 0)

return null;

PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.size(), new Comparator<ListNode>() {

@Override

public int compare(ListNode o1, ListNode o2) {

return o1.val - o2.val;

}

});

for (int i = 0; i < lists.size(); i++) {

if (lists.get(i) != null)

queue.add(lists.get(i));

}

ListNode head = new ListNode(0);

ListNode p = head;

while (!queue.isEmpty()) {

ListNode node = queue.poll();

p.next = node;

if (node.next != null)

queue.add(node.next);

p = p.next;

}

return head.next;

}

Complexity

Recursive version: We have T(n) = 2T(n/2) + kn. So the complexity is O(kn logn). The depth of the recursive function is O(log n).

Priority queue version: Every time we add a new element to the queue, it costs O(log n). And we have kn elements. So the complexity is O(kn logn) + O(kn) = O(kn logn). And the space complexity is only $O(n)$.