0023 Merge k Sorted Lists

0023 Merge k Sorted Lists#

Problem#

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.

Examples#

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 <= 104
0 <= lists[i].length <= 500
-104 <= lists[i][j] <= 104
lists[i] is sorted in ascending order.
The sum of lists[i].length will not exceed 104.

Analysis#

This is similar to merge 2 sorted lists, but the difficulty is how to quickly get the minimum from k nodes.

  • one straightfoward way is to use min heap tree or priority quque

Solution#

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

def build(A):
    dummy = Node()

    if not A:
        return dummy.next
    
    prev = dummy
    for a in A:
        cur = Node(a)
        prev.next = cur 
        prev = cur
    
    return dummy.next 

def linkedListToList(head):
    res = []
    while head:
        res.append(head.val)
        head = head.next
    return res

def mergeKLists(lists):
    pass
Contents