problem

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

solution

对于这个问题&＃xff0c;有这样两种主要的思路&＃xff1a;

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

第一种思路

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

ps&＃xff1a;要想到使用优先队列这个数据结构&＃xff0c;灵活使用tuple的比较。

from Queue import PriorityQueue
class Solution(object):def mergeKLists(self, lists):dummy &＃61; ListNode(0)tail &＃61; dummyq &＃61; PriorityQueue()for i in lists:if i:q.put((i.val, i))while not q.empty():minNode &＃61; q.get()[1]tail.next &＃61; minNodetail &＃61; tail.nextif minNode.next:q.put((minNode.next.val,minNode.next))tail.next &＃61; Nonereturn dummy.next

第二种思路

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

class Solution(object):def mergeKLists(self, lists):amount &＃61; len(lists)interval &＃61; 1while interval for i in range(0, amount - interval, interval * 2):lists[i] &＃61; self.merge2Lists(lists[i], lists[i &＃43; interval])interval *&＃61; 2return lists[0] if amount > 0 else listsdef merge2Lists(self, l1, l2):head &＃61; point &＃61; ListNode(0)while l1 and l2:if l1.val <&＃61; l2.val:point.next &＃61; l1l1 &＃61; l1.nextelse:point.next &＃61; l2l2 &＃61; l1l1 &＃61; point.next.nextpoint &＃61; point.nextif not l1:point.next&＃61;l2else:point.next&＃61;l1return head.next

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