题解 | #合并k个已排序的链表#

合并k个已排序的链表

https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 
# @param lists ListNode类一维数组 
# @return ListNode类
#
class Solution:
    def mergeKLists(self , lists: List[ListNode]) -> ListNode:
        # write code here
        # 借助数组,然后数组排序 再创建新的链表
        num = []
        for head in lists:
            while head:
                num.append(head.val)
                head = head.next

        if num is None:
            return None
        num.sort()
        # 定义新的链表
        newLinks =cur= ListNode(0)
        for i in range(len(num)):
            cur.next = ListNode(num[i])
            cur = cur.next
        return newLinks.next

分享解题思路:

借助数组实现快速排序,然后建立新的链表,从新串起来;

首先创建空数组 num= [],此时开始将所有的输入链表的值填充到num中,注意链表中保存到每个元素是一个链表,而链表中有包含有多个node(值)因此除了需要遍历lists还需要遍历lists中的链表,因此外层用for 内层用while

for head in lists:

while head: #判断是否为空链表

num.append(head.val)

head = head.next #链表中的下一个元素

if num is None: # 若得到的num为空,则返回None

return None

num.sort() #进行排序

newLinks=cur = ListNode(0) #创建新链表

for i in range(len(num)): # 利用新链表将数组中的元素串起来

cur.next = ListNode(num[i]) # 串

cur = cur.next # 移动cur

return newLinks

完结撒花!

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-11 12:10
点赞 评论 收藏
分享
程序员小白条:太晚了,看别人找到实习了才投的话,自己本身就没啥准备,计划太晚咯,只能吞苦果子
点赞 评论 收藏
分享
07-09 12:12
门头沟学院 Java
5月底投简历7月初开奖收获秋招第一个offer,虽然白菜价,但至少能保底了
土木转行ing:土木博士想转图像,最后拿了 tp 提前批 sp 最低档,感觉性价比不高
TP-LINK开奖132人在聊
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务