3. Merge K Sorted Linked Lists

This problem was recently asked by Twitter: You are given an array of k sorted singly linked lists. Merge the linked lists into a single sorted linked list and return it.

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

  def __str__(self):
    c = self
    answer = ""
    while c:
      answer += str(c.val) if c.val else ""
      c = c.next
    return answer

def merge(lists):
  # Fill this in.

a = Node(1, Node(3, Node(5)))
b = Node(2, Node(4, Node(6)))
print merge([a, b])
# 123456

def merge(lists):
  total = 0
  for i in range(len(lists)):
    total += len(lists[i])

  result = Node(0)
  min = (-1, -1)

  while total > 0:
    for i in range(len(lists)):
      node = lists[i]
      if min[0] == -1:
        min = (i, node.value)
       else:
        if node.value <= min:
          min = (i, node.value)
    current_min_node = lists(min[0])
    result.next = current_min_node
    # remove cur min node from the list
    lists(min[0]) = current_min_node.next
    current_min_node.next = None
    # reset
    min = (-1, -1)
    total -= 1


  return result.next

Lists 中有k個list, 每個長度假設為n

• maintain a pointer for each linked list that indicates where we are in that list. Then each time, simply find the minimum value from all the pointers and add that to our output linked list, and advance that pointer

def merge(lists): # total: O(kn * k)
  newHead, current = Node(-1)
  while any(lst is not None for lst in lists): #kn
    cur_min, i = min((lst.val, i) for i, lst in enumerate(lists) if lst is not None) #k
    list[i] = list[i].next
    current.next = Node(current_min)
    current = current.next

  return newHead.next

• The most optimal solution involves the use of a minheap for the pointers

• We simply grab the element at the top of the heap, and advance the corresponding pointer and add the new value to the heap.

def merge(lists): # total: O(kn * logk)
  newHead, current = Node(-1)
  heap = [(lst.val, i) for i, lst in enumerate(lists)]
  heapq.heapify(heap) # k
  while heap: # kn
    current_min, i = heapq.heappop(heap) # 1

    current.next = Node(current_min)
    current = current.next

    if list[i] is not None:
      list[i] = list[i].next
      if list[i]: # logk
        heapq.heappush(heap, (list[i].val, i))
    return new_head.next