题解 | #合并k个已排序的链表#

仿归并排序：

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#
# 
# @param lists ListNode类一维数组 
# @return ListNode类
#
class Solution:
    def mergeKLists(self , lists ):
        # write code here
        # base case
        if len(lists) <= 1:
            if len(lists) == 1:
                return lists [0]
            else:
                return None
        
        iMid = int(len(lists)/2)
        pMergedLeft = self.mergeKLists(lists[:iMid])
        pMergedRight = self.mergeKLists(lists[iMid:])
        if pMergedLeft == None:
            return pMergedRight
        if pMergedRight == None:
            return pMergedLeft
        
        if pMergedLeft.val <= pMergedRight.val:
            pTemp = pMergedLeft
            pMergedLeft = pMergedLeft.next
        else:
            pTemp = pMergedRight
            pMergedRight = pMergedRight.next
        pRes = pTemp
        
        while pMergedLeft != None and pMergedRight != None:
            if pMergedLeft.val <= pMergedRight.val:
                pTemp.next = pMergedLeft
                pMergedLeft = pMergedLeft.next
            else:
                pTemp.next = pMergedRight
                pMergedRight = pMergedRight.next
            pTemp = pTemp.next
        
        if pMergedLeft != None:
            pTemp.next = pMergedLeft
        else:
            pTemp.next = pMergedRight
        return pRes