概述
题目描述
给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
Leetcode原题地址:https://leetcode-cn.com/problems/merge-k-sorted-lists/
测试用例
- 示例1
输入: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
- 示例2
输入:lists = []
输出:[]
- 示例3
输入:lists = [[]]
输出:[]
代码实现
- 顺序合并
前面我们实现过2个升序链表的合并,K个链表的合并其实就是2个链表合并的升级版。定义一个最终的链表,先合并第一个和第二个,然后再合并第三…
from typing import List
class ListNode:
def __init__(self,val=0,next=None):
if isinstance(val,int):
self.val = val
self.next = next
elif isinstance(val,list):
self.val = val[0]
self.next = None
head = self
for i in val[1:]:
node = ListNode(i,None)
head.next = node
head = head.next
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
def mergeTwoLists(a: ListNode, b: ListNode):
merge = ListNode(-1)
head = merge
while a and b:
if a.val > b.val:
head.next = b
b = b.next
else:
head.next = a
a = a.next
head = head.next
head.next = a if a else b
return merge.next
if len(lists) == 0:
return None
res = None
for i in range(0,len(lists)):
res = mergeTwoLists(res,lists[i])
return res
lists = [[1,4,5],[1,3,4],[2,6]]
l_nodes = []
for l in lists:
listnode = ListNode(l)
l_nodes.append(listnode)
solution = Solution()
merge = solution.mergeKLists(l_nodes)
while merge:
print(merge.val)
merge = merge.next
- 分治法合并
在使用顺序合并的时候存在很多重复的操作,从而导致合并的时间会很长,其实我们可以先将整个链表分成两大块,然后再继续切分,最后分到左边和右边的链表长度为1时,再往上进行合并
class Solution:
def mergeTwoList(self,a:ListNode,b:ListNode):
merge = ListNode(-1)
head = merge
while a and b:
if a.val > b.val:
head.next = b
b = b.next
else:
head.next = a
a = a.next
head = head.next
head.next = a if a else b
return merge.next
def merge(self,left,right):
if left == right:
return self._lists[left]
if left > right:
return None
middle = (left+right) // 2
return self.mergeTwoList(self.merge(left,middle),self.merge(middle+1,right))
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
self._lists = lists
return self.merge(0,len(lists)-1)
参考:合并K个排序链表
最后
以上就是含糊大船为你收集整理的Python实现合并K个升序链表的全部内容,希望文章能够帮你解决Python实现合并K个升序链表所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复