题目

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

翻译

合并k个有序的链表

Hints

Related Topics: LinkedList, Divide and Conquer, Heap

Solution1：Divide and Conquer

参考 归并排序-*

思路：分治，先分成两个子任务，然后递归子任务，最后回溯回来..这里就可以将k个链表分成两半，再继续划分，直到最后还剩下2个链表就利用之前做的 Merge Two Sorted Lists 来合并

Solution2：Heap

用到了堆的数据结构（太菜了想不到，还是要学习一个）

学习一下 堆的数据结构，维护一个大小为k的堆，每次取堆顶的最小元素放到结果中，然后再把该元素的下一个元素放到堆中，重新维护好；因为每个链表都是有序的，每次都是取堆中最小的元素，这样当所有的链表都读完的时候，result链表中就是所有的元素从小到大排列了

Solution2要读一遍所有元素：即 k*n 次，读取元素又将新元素插入堆中是 logn的复杂度，所有最后时间复杂度是O(nk logn)..

代码

Java

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) { val = x; }

 * }

 */

//Solution1

class Solution {

    public ListNode mergeKLists(ListNode[] lists) {

        return Divide(lists, 0, lists.length-1);

    }

    public static ListNode Divide(ListNode[] lists, int start, int end){

        if(start==end)  return lists[start];

        if(start<end){

            int middle = (start+end)/2;

            ListNode l1 = Divide(lists,start,middle);

            ListNode l2 = Divide(lists,middle+1,end);

            return merge2Lists(l1, l2);

        }else

            return null;

    }

    public static ListNode merge2Lists(ListNode l1,ListNode l2){

        if(l1==null)    return l2;

        if(l2==null)    return l1;

        if(l1.val<l2.val){

            l1.next = merge2Lists(l1.next,l2);

            return l1;

        }else{

            l2.next = merge2Lists(l1,l2.next);

            return l2;

        }

    }

}

Python

# Definition for singly-linked list.

# class ListNode(object):

#     def __init__(self, x):

#         self.val = x

#         self.next = None

//Solution2

from Queue import PriorityQueue

class Solution(object):

    def mergeKLists(self, lists):

        """

        :type lists: List[ListNode]

        :rtype: ListNode

        """

        dummy = curr = ListNode(None)

        q = PriorityQueue()

        for node in lists:

            if node:    q.put((node.val,node));

        while q.qsize()>0:

            curr.next = q.get()[1]

            curr = curr.next

            if curr.next:

                q.put((curr.next.val,curr.next))

        return dummy.next

一些用途

在分布式系统中非常常见，来自不同client的sorted list要在central server上面merge起来

一些参考

leetcode discuss

归并排序-*

数据结构之“堆”

Merge k Sorted Lists -- LeetCode