Leetcode @merge k sorted lists python

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Hidden:
lists contain 0~k ListNode, the maximum number in each ListNode queue is n.
return one ListNode,which is the head of the long list.
corner case: [{}], [{},{}]

Analysis:
There are two ways to solve this problem. One use recursive call, the essence is the same as merge sort.
we treat 0,1....n-1 as merge sort. use mid as the dividing point. The time is T (K) = T( K/2) +O( nK), so T= O(nKlogK)

Another way is to use min heap as size K, and each time pop the min , insert the next one in the list. The time is O(nKlogK)
Code for recursive: 

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

class Solution:
    # @param a list of ListNode
    # @return a ListNode
    
    def mergeKLists(self, lists):
        if not lists:
            return None
        else:
            return self.mergeList(lists, 0, len(lists)-1)
        
    def mergeList(self, lists, left, right):
        # return a node with merged two lists
        if left<right:
            mid= (left+right)//2
            return self.merge(self.mergeList(lists, left, mid), self.mergeList(lists, mid+1, right))
        else:
            return lists[left]
    
    def merge(self, node1, node2):
        dummy =ListNode(0)
        pointer=dummy
        while node1!=None and node2!=None:
            if node1.val>node2.val:
                pointer.next=node2
                node2=node2.next
            else: pointer.next=node1; node1=node1.next
            pointer=pointer.next
        if node1==None:
            pointer.next=node2
        if node2==None:
            pointer.next=node1
        return dummy.next

Code for Min heap:

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

class Solution:
    # @param a list of ListNode
    # @return a ListNode
    
    def mergeKLists(self, lists):
        #   this method use a min heap
        heap =[]
        for node in lists:
            if node:
                heap.append((node.val,node))
        heapq.heapify(heap);head=ListNode(0);curr=head
        while heap:
            pop=heapq.heappop(heap)
            curr.next=pop[1]
            curr=curr.next
            if pop[1].next: heapq.heappush(heap,(pop[1].next.val,pop[1].next))
        return head.next