leetcode 23
Published:
题目23
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
输入样例
输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6
解析
- 思路A：参考合并两个有序链表，每次合并两个，一直到合并完所有链表
- 思路B：每次对k个链表的最小元素排序，然后把最小值排到结果链表后面，实现过程中用到最小堆，也称作优先队列
实际解题过程中，思路A和思路B的时间复杂度都可以压缩到 $O(N*log\ K)$，但是思路B需要使用额外空间，而且如需自己实现最小堆，实现过程较为复杂，建议优先实现思路A
题解
Python 实现优先队列方案，使用heapq
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
import heapq
dummy=ListNode(0)
p=dummy
heapx=[]
for kidx in range(len(lists)):
if lists[kidx]:
heapq.heappush(heapx,(lists[kidx].val,kidx))
lists[kidx]=lists[kidx].next
while heapx:
val,idx=heapq.heappop(heapx)
p.next=ListNode(val)
p=p.next
if lists[idx]:
heapq.heappush(heapx,(lists[idx].val,idx))
lists[idx]=lists[idx].next
return dummy.next
面试中实际写出来的原版方案A
def merge2(A,B):
if not A:
return B
if not B:
return A
result=Node(None)
curNode=result
while(A!=None or B!=None):
if A.val>B.val:
curNode.next=A
A=A.next
else:
curNode.next=B
B=B.next
curNode=curNode.next
if A:
curNode.next=A
else:
curNode.next=B
return result.next
def merge(x: List[Node]) -> Node:
if len(x)==0:
return None
elif len(x)=1:
return x[0]
while len(x)>1:
x=x[2:].append(merge2(x[0],x[1]))
return x[0]
修改后可AC的思路A
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def submerge(self,A:ListNode,B:ListNode)->ListNode:
if not A and not B:
return None
elif not B:
return A
elif not A:
return B
result=ListNode(0)
curNode=result
while A and B:
if A.val<B.val:
curNode.next=A
A=A.next
else:
curNode.next=B
B=B.next
curNode=curNode.next
if A:
curNode.next=A
else:
curNode.next=B
return result.next
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
if len(lists)==0:
return None
elif len(lists)==1:
return lists[0]
while len(lists)>1:
result=self.submerge(lists[0],lists[1])
lists=lists[2:]
lists.append(result)
return lists[0]