题解 | #合并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
完结撒花!