Skip to main content

Merge k Sorted Lists

Question​

Given an array of 'k' sorted linked lists, create a new sorted singly-linked list that contains all 'k' lists' nodes in sorted order.

Example 1
Input: 
list1: [1, 4, 7]
list2: [2, 5, 8]
list3: [3, 6, 9]

Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]

Solution​

all//Merge k Sorted Lists.py


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

def mergeKLists(lists):
    head = point = ListNode(0)
    q = PriorityQueue()

    for l in lists:
        if l:
            q.put((l.val, l))

    while not q.empty():
        val, node = q.get()
        point.next = ListNode(val)
        point = point.next
        node = node.next
        if node:
            q.put((node.val, node))
    return head.next