problem

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

solution

对于这个问题，有这样两种主要的思路：

从这k个链表中找出最小的连接到dummy node上，知道所有链表为空。把merge k简化成merge 2，也就是每次只merge两个链表，知道lists中只剩下一个链表。

第一种思路

这个思路的可优化的地方就是如何找到最小的元素，这里可以使用优先队列，另外在优先队列中我们想要根据val的大小找到其对应的指针，所以我们把(node.val, node)加入队列（因为python中可以直接比较tuple的大小）

ps：要想到使用优先队列这个数据结构，灵活使用tuple的比较。

from Queue import PriorityQueue class Solution(object): def mergeKLists(self, lists): dummy = ListNode(0) tail = dummy q = PriorityQueue() for i in lists: if i: q.put((i.val, i)) while not q.empty(): minNode = q.get()[1] tail.next = minNode tail = tail.next if minNode.next: q.put((minNode.next.val,minNode.next)) tail.next = None return dummy.next

第二种思路

把问题简化为merge 2的问题，这种思路可以每次递归值归并前两个，或是或是每次把相邻的两个都归并了，后者的栈的深度要更小。

class Solution(object): def mergeKLists(self, lists): amount = len(lists) interval = 1 while interval < amount: for i in range(0, amount - interval, interval * 2): lists[i] = self.merge2Lists(lists[i], lists[i + interval]) interval *= 2 return lists[0] if amount > 0 else lists def merge2Lists(self, l1, l2): head = point = ListNode(0) while l1 and l2: if l1.val <= l2.val: point.next = l1 l1 = l1.next else: point.next = l2 l2 = l1 l1 = point.next.next point = point.next if not l1: point.next=l2 else: point.next=l1 return head.next

这种解法可能因为不需要空间上的移动，效率要比第一种解法高。