text: """ 
  Merge K Linked List Using A PQ(essentiall linear min heap)
  """
  
  class Solution(object):
    def mergeKLists(self, lists):
      """
      :type lists: List[ListNode]
      :rtype: ListNode
      """
      amount = len(lists)
      interval = 1
      while interval < amount:
        for i in range(0, amount- interval, interval*2):
          lists[i] = self.merge2Lists(lists[i], lists[i+interval])
          #merging the two lists in place with a widening interval 
        interval *=2
      return lists[0] if amount > 0 else lists
  
    def merge2Lists(self, l1, l2):
      head = point = ListNode(0)
      while l1 and l2:
        if l1.val <= l2.val:
          point.next = l1
          l1 = l1.next
        else:
          point.next = l2
          l2 = l1 #chaining to link merge on current spaced interval
          #divide and conquer(but since it is already divided, it is just the conquer)
          l1 = point.next.next 
        point = point.next
      if not l1: 
        point.next = l2
      else:
        point.next = l1
      return head.next