合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。
数据范围:节点总数 ,每个节点的val满足
要求:时间复杂度
class Solution: def mergeKLists(self, lists): """ :type lists: List[ListNode] :rtype: ListNode """ # 堆队列算法,比如优先队列 import heapq pre = ListNode(-1) cur = pre # 优先队列 head = [] # 遍历所有链表 for i in range(len(lists)): if lists[i]: # 将链表头结点放入优先队列中,放入头结点,就相当于放入了整个链表!! heapq.heappush(head, (lists[i].val, i)) # 各链表首指针往后移动 lists[i] = lists[i].next # 合并队列中已有的节点 while head: # 取得节点值域,及其在对应链表中节点的下标位置 # 由于优先队列的性质:heappop()的就是当前队列中最小元素 val, index = heapq.heappop(head) # 构造节点并入结果链表 cur.next = ListNode(val) # 指针往后顺移 cur = cur.next # 若最小节点对应的链表不为空 if lists[index]: # 将对应链表的下一个节点入队 heapq.heappush(head, (lists[index].val, index)) # 遍历该链表的指针往后顺移 lists[index] = lists[index].next return pre.next
class Solution: def mergeKLists(self , lists ): # write code here if not lists: return None if len(lists) <= 1: return lists[0] if len(lists) == 2: return self.mergeTwoLists(lists[0], lists[1]) idx = len(lists) // 2 left = self.mergeKLists(lists[:idx]) right = self.mergeKLists(lists[idx:]) return self.mergeKLists([left, right]) def mergeTwoLists(self , p1, p2): # write code here head = ListNode(0) curr = head while p1 and p2: if p1.val <= p2.val: curr.next = p1 p1 = p1.next else: curr.next = p2 p2 = p2.next curr = curr.next if p2: curr.next = p2 if p1: curr.next = p1 return head.next
def __init__(self, x): self.val = x self.next = None # # # @param lists ListNode类一维数组 # @return ListNode类 # class Solution: def mergeKLists(self , lists ): # write code here newHead=ListNode(0) cur=newHead lists=[x for x in lists if x] while lists: lists=sorted(lists,key=lambda x:x.val) cur.next=lists[0] cur=cur.next lists[0]=lists[0].next lists=[x for x in lists if x] return newHead.next
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # # @param lists ListNode类一维数组 # @return ListNode类 # class ListNode: def __init__(self,x): self.val=x self.next=None class Solution: def mergetwolist(self,l1,l2): #对k条链表进行合并,可以思考采用的方法是两两合并的方法 head=ListNode(0) p=head while l1 and l2: if l1.val<l2.val: p.next=l1 l1=l1.next else: p.next=l2 l2=l2.next p=p.next if l1: p.next=l1 elif l2: p.next=l2 return head.next def mergeKLists(self , lists ): # write code here if not lists: return None k=len(lists) if k==1: return lists[0] if k==2: return self.mergetwolist(lists[0],lists[1]) s1=self.mergeKLists(lists[:(k//2)]) s2=self.mergeKLists(lists[(k//2):]) return self.mergetwolist(s1,s2)采用两两合并的方法,主调用里采用递归,合并的时候采用两两合并的方式,实现全体链表的合并。