23 Merge k Sorted Lists

23. Merge k Sorted Lists

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

分析& 代码

因为snapchat有一道题，merge log

“用电脑写一个program，可以把多个log file合并成一个，按照每个log的时间顺序排，要能运行。这不就是都读进来然后排个序然后输出吗！然后我用了大量的时间。。。搜索如何用c++进行file io。。。太丢人了。主要网速太慢！写完了给他看，能运行。OK。然后他问如何改进。我突然想到这些log file是排好序的，就说可以merge sort的方法merge进来，每个文件保持一个pointer就行。后来他问如果有很多log file呢，min heap完事儿。”

from 面经

其实就是merge k sorted lists吧

使用一个PriorityQueue，每次抽出最小的点，维持每个list的头

public ListNode mergeKLists(ListNode[] lists) {
    if(lists.length == 0) {
        return null;
    }
    ListNode dummy = new ListNode(-1);
    ListNode head = dummy;
    PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {
        public int compare(ListNode l1, ListNode l2) {
            return l1.val - l2.val;
        }
    });
    for(int i = 0; i < lists.length; i++) {
        if(lists[i] != null) {
            pq.offer(lists[i]);
        }
    }
    while(!pq.isEmpty()) {
        head.next = pq.poll();;
        head = head.next;
        if(head.next != null) {
            pq.offer(head.next);
        }
    }
    return dummy.next;
}