分类：LinkedList
考察知识点：LinkedList 分治 PriorityQueue
最优解时间复杂度：**O(nlogk) **
23. Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6
代码：
分治方法:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
if len(lists)==0:
return []
return self.sort(lists,0,len(lists)-1)
def sort(self,lists,lo,hi):
if lo>=hi:
return lists[lo]
mid=(hi-lo)//2+lo
l1 = self.sort(lists,lo,mid)
l2 = self.sort(lists,mid+1,hi)
return self.merge(l1,l2)
def merge(self,l1,l2):
if l1==None:
return l2
elif l2==None:
return l1
else:
if(l1.val<=l2.val):
l1.next=self.merge(l1.next,l2)
return l1
else:
l2.next=self.merge(l1,l2.next)
return l2
PriortyQueue方法:(Python没见过有这种方法就用data,sort替代了)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
if len(lists)==0:
return []
sorted_lists=[]
for each in lists:
if each!=None:
sorted_lists.append(each)
sorted_lists=sorted(sorted_lists,key=lambda x:x.val)
dummy=ListNode(0)
p=dummy
while(len(sorted_lists)!=0):
cur=sorted_lists.pop(0)
p.next=cur
p=p.next
if(cur.next!=None):
sorted_lists.append(cur.next)
sorted_lists=sorted(sorted_lists,key=lambda x:x.val)
return dummy.next
讨论：
1.这道题的重点是它的时间复杂度是O(nlogk),k是指lists中LinkedList的数量
2.有两种方法一种是分治，还有一种是PriorityQueue,两种时间复杂度一样
3.这道题如果在面试中，面试官一般会喜欢考察PriorityQueue的方法
4.Python没有这个PriorityQueue的结构，我用sortedlist代替了，其实原理是一样的
分治
PriorityQueue
