解题思路:每次从这几个链表中选择一个最小的值,加入到head值指向的合并链表的链表尾部,选择完毕就令当前被选择的结点(在被选择的升序链表中)指向下一个next结点,并进行下一轮的比较。如果其中有一个升序链表先被选完了,就将该None值pop掉,直到所有的升序链表都被选择完毕且被pop掉时,就得到了合并后的链表结果。
代码如下:
# 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[Optional[ListNode]]) -> Optional[ListNode]:
k = len(lists)
listp = [lists[i] for i in range(k)]
head = None
pnode_pre = None
#排除掉空列表的情况
for i in range(k-1,-1,-1):
if listp[i] is None:
listp.pop(i)
# 还有结点可以选择的话
while listp!=[]:
# 找到当前listp中存在的最小的值和下标,并且移动到选择完的下一个
minval = listp[0].val
index = 0
for i in range(1,len(listp)):
if minval > listp[i].val:
minval = listp[i].val
index = i
if listp[index].next is None:
listp.pop(index)
else:
listp[index] = listp[index].next
# 前一个结点指向新建的节点
node = ListNode(minval, None)
if head is None:
head = node
pnode_pre = node
else:
pnode_pre.next = node
pnode_pre = node
return head
结果如下:
看到结果发现是真的慢,想了想发现有很多可以优化的地方:
空间复杂度上:
首先不需要使用listp来进行存储,题目中给的就是listp列表的作用
同时,也不需要再次建立一个Linknode对象,直接使用输入中链接的就可以。
试了一下:
# 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[Optional[ListNode]]) -> Optional[ListNode]:
k = len(lists)
head = None
pnode_pre = None
#排除掉空列表的情况
for i in range(k-1,-1,-1):
if lists[i] is None:
lists.pop(i)
# 还有结点可以选择的话
while lists!=[]:
# 找到当前listp中存在的最小的值和下标,并且移动到选择完的下一个
minval = lists[0].val
index = 0
for i in range(1,len(lists)):
if minval > lists[i].val:
minval = lists[i].val
index = i
if lists[index].next is None:
node = lists.pop(index)
else:
node = lists[index]
lists[index] = lists[index].next
# 前一个结点指向新建的节点
if head is None:
head = node
pnode_pre = node
else:
pnode_pre.next = node
pnode_pre = node
return head
结果空间复杂度降下去了:
时间复杂度上,应该要减少比较的次数,如果每次都需要从k个结点中选择一个最小的,确实难以减少比较次数,所以想着做类似于合并排序算法,两个两个一组排序再合并。
转念一想,最后要的是所有值的最终的排序,那我直接把所有值得到后再排序岂不是更快?
代码如下:
# 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[Optional[ListNode]]) -> Optional[ListNode]:
allnum = []
for i in range(len(lists)):
while lists[i] is not None:
allnum.append(lists[i].val)
lists[i] = lists[i].next
allnum.sort()
head = None
pnode_pre = None
for i in range(len(allnum)):
node = ListNode(allnum[i], None)
if head is None:
head = node
pnode_pre = node
continue
pnode_pre.next = node
pnode_pre = node
return head
结果如下:
- THE END -
最后修改:2022年8月16日
非特殊说明,本博所有文章均为博主原创。
如若转载,请注明出处:https://wangyuanzhuo.top/t23-%e5%90%88%e5%b9%b6k%e4%b8%aa%e5%8d%87%e5%ba%8f%e9%93%be%e8%a1%a8/