23.?合并K個(gè)排序鏈表
合并k?個(gè)排序鏈表，返回合并后的排序鏈表谴返。請(qǐng)分析和描述算法的復(fù)雜度煞肾。
示例:
輸入:[? 1->4->5,? 1->3->4,? 2->6]輸出:1->1->2->3->4->4->5->6
# class ListNode:
#? ? def __init__(self, x):
#? ? ? ? self.val = x
#? ? ? ? self.next = None
import numpy as np
class Solution:
? ? isFirst = True
? ? def mergeKLists(self, lists):
? ? ? ? """
? ? ? ? :type lists: List[ListNode]
? ? ? ? :rtype: ListNode
? ? ? ? """
? ? ? ? lenght = lists.__len__()
? ? ? ? arr = []
? ? ? ? while lenght >0:
? ? ? ? ? ? if lists[lenght-1]==None:
? ? ? ? ? ? ? ? lists.pop(lenght-1)
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? arr.append(0)
? ? ? ? ? ? lenght-=1
? ? ? ? lenght = lists.__len__()
? ? ? ? if lenght==0:
? ? ? ? ? ? return
? ? ? ? list_head = ListNode(-1)
? ? ? ? list_node = ListNode(0)
? ? ? ? list_head.next = list_node
? ? ? ? self.isFirst =True
? ? ? ? # arr = np.zeros(lenght,dtype=int)
? ? ? ? list_node = self.digui(lists,list_node,arr )
? ? ? ? return list_node
? ? def digui(self, lists, list_node, arr):
? ? ? ? lenght = lists.__len__()
? ? ? ? if lenght == 1:
? ? ? ? ? ? list_node.next = lists[0]
? ? ? ? ? ? return list_node.next
? ? ? ? while lenght >0 and self.isFirst:
? ? ? ? ? ? arr[lenght-1] = lists[lenght-1].val
? ? ? ? ? ? lenght-=1
? ? ? ? self.isFirst = False
? ? ? ? # index = arr.argmin()
? ? ? ? index = arr.index(min(arr))
? ? ? ? node = ListNode(arr[index])
? ? ? ? list_node.next = node
? ? ? ? if lists[index].next == None:
? ? ? ? ? ? lists.pop(index)
? ? ? ? ? ? # arr = np.delete(arr,index,axis=0)
? ? ? ? ? ? arr.pop(index)
? ? ? ? else:
? ? ? ? ? ? lists[index] = lists[index].next
? ? ? ? ? ? arr[index] = lists[index].val
? ? ? ? self.digui(lists, list_node.next, arr)
? ? ? ? return list_node.next
