python 合并k个有序链表，,from heapq

python 合并k个有序链表，,from heapq

from heapq import heappush, heappopclass Solution:    def mergeKLists(self, lists):        q = []        for i,head in enumerate(lists):            if head:                heappush(q, (head.val, i, head))        node = dummy = ListNode(0)        while q:            val, i, pop_node = heappop(q)            print(val)            node.next = ListNode(val)            node = node.next            next_node = pop_node.next            if next_node:                heappush(q, (next_node.val, i, next_node))        return dummy.next

　　

为啥有i？？？？？？？？？？？理由见后、

另外PQ也有这个问题

# Definition for singly-linked list.# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = Noneimport queueclass Solution:    def mergeKLists(self, lists: List[ListNode]) -> ListNode:        q = queue.PriorityQueue()        for i,head in enumerate(lists):            if head:                q.put((head.val, i, head))                node = dummy = ListNode(0)        while not q.empty():            val, i, pop_node = q.get()            node.next = ListNode(val)            node = node.next            next_node = pop_node.next            if next_node:                q.put((next_node.val, i, next_node))        return dummy.next

　　

python 3 heappush Line 13: TypeError: ‘<‘ not supported between instances of ‘ListNode‘ and ‘ListNode‘

出现原因：

@cbmbbz In the event that two or more of the lists have the sameval, this code will error out since thequeuemodule will compare the second element in the priority queue which is aListNodeobject (and this is not a comparable type).

To solve for this issue, I have stored(node.val, list_idx, node)to account for this edge case.

from queue import PriorityQueue# Definition for singly-linked list.# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution:    def mergeKLists(self, lists):        k = len(lists)        q = PriorityQueue(maxsize=k)        dummy = ListNode(None)        curr = dummy        for list_idx, node in enumerate(lists):            if node: q.put((node.val, list_idx, node))        while q.qsize() > 0:            poped = q.get()            curr.next, list_idx = poped[2], poped[1]            curr = curr.next            if curr.next: q.put((curr.next.val, list_idx, curr.next))        return dummy.next

48Show4repliesReplyShareReportonedingz25

Last Edit: October 11, 2018 9:42 PM

Read More

Python3 env will getTypeError: ‘<‘ not supported between instances of ‘ListNode‘ and ‘ListNode‘
if there are duplicate values in the list. Works in Python env.

python 合并k个有序链表