Skip to main content

Merge K Sorted Lists

Question​

Two bar problem​

find best area among ....

""" You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

========================================================= Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6]

Explanation: The linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted list: 1->1->2->3->4->4->5->6

========================================================= Example 2:

Input: lists = [] Output: [] Example 3:

Input: lists = [[]] Output: []

========================================================= Constraints:

k == lists.length 0 <= k <= 10^4 0 <= lists[i].length <= 500 -10^4 <= lists[i][j] <= 10^4 lists[i] is sorted in ascending order. The sum of lists[i].length will not exceed 10^4. """

Solution​

heap/Merge K Sorted Lists.py
import heapq


class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    def print(self):
        print(self.val)
        if self.next:
            self.next.print()


def mergeKLists(lists):
    head = ListNode(None)
    curr = head
    h = []

    for i in range(len(lists)):
        if lists[i]:
            heapq.heappush(h, (lists[i].val, i))
            lists[i] = lists[i].next

    while h:
        val, i = heapq.heappop(h)
        curr.next = ListNode(val)
        curr = curr.next

        #print(curr)

        if lists[i]:
            heapq.heappush(h, (lists[i].val, i))
            lists[i] = lists[i].next

    return head.next


h1 = ListNode(1, ListNode(4, ListNode(5)))
h2 = ListNode(1, ListNode(3, ListNode(4)))
h3 = ListNode(2, ListNode(6))

result = mergeKLists([h1, h2, h3])


#print(result)
Stepcurr
1<main.ListNode object at 0x000001967CA93D30>
2<main.ListNode object at 0x000001967CAD5400>
3<main.ListNode object at 0x000001967CABE820>
4<main.ListNode object at 0x000001967CA93E20>
5<main.ListNode object at 0x000001967CA93E50>
6<main.ListNode object at 0x000001967CA93FD0>
7<main.ListNode object at 0x000001967CA93D90>
8<main.ListNode object at 0x000001967E241BB0>
result
<main.ListNode object at 0x000001967CA93D30>