难度: 困难(Hard)

题目：

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

思路：
这个题首先想到的是与合并两个有序链表一样，维护k个指针分别指向那k个链表，每次从中选出一个最小的加入到已有序链表尾，然后那个指针后移。这种做法的时间复杂度为o(nk)，提交之后，结果超时。然后想到当某个指针为空时，便不再需要保存这个指针，修改代码为动态删除空指针也超时，因为本质上时间复杂度还是o(nk)。合并k个链表其实可以分解为分别合并前一半和后一半，然后再将这两个结果合并，也就是分治的思想。采用分治的话，层次为log(n)，每次合并都为o(n)，所以最后的时间复杂度为o(nlog(n))。

代码：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):

    def mergeTwo(self, l1, l2):
        head = ListNode(None)
        p = head
        while l1!=None and l2!=None:
            p.next = l1
            if l1.val < l2.val:
                p = p.next
                l1 = l1.next
            else:
                p.next = l2
                p = p.next
                l2 = l2.next
        if l1 != None:
            p.next = l1
        if l2 != None:
            p.next = l2
        return head.next

    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        if lists==None or len(lists)==0:
            return None
        if len(lists) == 1:
            return lists[0]
        l = self.mergeKLists(lists[0:len(lists)/2])
        r = self.mergeKLists(lists[len(lists)/2:])
        return self.mergeTwo(l,r)