题目：
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)
