8 lines Python with generators and heapq.merge


  • 1

    Solution 1

    Building the new list with just the values from the old ones, leaving the old lists intact.

    def mergeKLists(self, lists):
        def vals(node):
            while node:
                yield node.val
                node = node.next
        dummy = last = ListNode(None)
        for val in heapq.merge(*map(vals, lists)):
            last.next = last = ListNode(val)
        return dummy.next
    

    Solution 2

    Building the new list with the nodes from the old ones.

    def mergeKLists(self, lists):
        def gen(node):
            while node:
                yield node.val, node
                node = node.next
        dummy = last = ListNode(None)
        for _, last.next in heapq.merge(*map(gen, lists)):
            last = last.next
        return dummy.next

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.