23.Merge k Sorted Lists

Tags: [heap], [min_heap], [list], [linked_list], [sort], [merge], [merge_sort]

Com: {fb}

Link: https://leetcode.com/problems/merge-k-sorted-lists/\#/description

Mergeksorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Solution: Min Heap

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        if not lists:
            return None

        fake_head = ListNode(-1)
        tmp = fake_head

        # dump all head nodes into min heap
        min_heap = []
        for head in lists:
            if head:
                min_heap.append((head.val, head))
        heapq.heapify(min_heap)

        while min_heap:
            _, curr_head = heapq.heappop(min_heap)
            new_head = curr_head.next

            curr_head.next = None
            tmp.next = curr_head
            tmp = tmp.next

            if new_head:
                heapq.heappush(min_heap, (new_head.val, new_head))

        return fake_head.next

Revelation:

• Leetcode may give [None] as the input, this is the reason why we do check the head is None or not when we put it into the min_heap.

Note:

• Time complexity = O(n + lg(n*k)), n is the number of linked list, k is the length of the longest linked list.