Merge K Linked List

出处

Merge k sorted linked lists to be one sorted list.

Solution

可以将k个sorted list想象成k个有序数据流,互相竞争插入到结果序列, 因此可以考虑使用一个最小值堆维护动态数据:将每个队头的元素加入一个堆,然后从堆中依次弹出最小数据。如果数据属于第i个list,则该list补充一个元素到堆。重复上述过程直到所有元素排序完成。事实上,该算法就是外排序算法的一个具体实现,区别仅仅在于这里略去了文件的读写操作。

Complexity

时间上,我们需要维护一个大小为k的最小值堆,每次维护复杂度O(logk),由于一共有n个数据,每个数据都会加入最小值堆,故总体时间复杂度O(nlogk)。由于每个list至少有一个数据,故n一定大于等于k。相比于完全无序的n个数据排序(所需时间O(nlogn)),我们的算法将复杂度降至O(nlogk)。原因在于数据是部分有序的。事实上,在通常面试中,如果数据已经部分有序,我们理应能够实现时间复杂度优于O(nlogn)的算法。

空间上,我们需要大小为k的最小值堆。同时,在不允许破坏原有链表的情况下,我们需要额外O(n)的空间构建新链表,故总体空间复杂度O(n+k)。如果可以直接修改原有数据的next指针,则总体空间复杂度即为O(k)。至于是否能够破坏原始数据,需要与面试官进行沟通。

Code

//  Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
 
    ListNode(int x) {
        val = x;
        next = null;
    }
}
 
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if (lists.size() == 0)
            return null;
 
        //PriorityQueue is a sorted queue
        PriorityQueue<ListNode> q = new PriorityQueue<ListNode>(lists.size(),
                new Comparator<ListNode>() {
                    public int compare(ListNode a, ListNode b) {
                        if (a.val > b.val)
                            return 1;
                        else if(a.val == b.val)
                            return 0;
                        else 
                            return -1;
                    }
                });
 
        //add first node of each list to the queue
        for (ListNode list : lists) {
            if (list != null)
                q.add(list);
        }
 
        ListNode head = new ListNode(0);
        ListNode p = head; // serve as a pointer/cursor
 
        while (q.size() > 0) {
            ListNode temp = q.poll();
            //poll() retrieves and removes the head of the queue - q. 
            p.next = temp;
 
            //keep adding next element of each list
            if (temp.next != null)
                q.add(temp.next);
 
            p = p.next;
        }
 
        return head.next;
    }
}