视频讲解

视频链接：https://www.bilibili.com/video/BV1cK4y1Q7th/
归并排序思路

import sys
sys.setrecursionlimit(1000000)
class Solution:
    def mergeKLists(self , lists ):
        if not lists: return
        n = len(lists)
        return self.merge(lists, 0, n - 1)

    def merge(self, lists, left, right):
        if left == right: return lists[left]
        mid = left + (right - left) // 2
        list1 = self.merge(lists, left, mid)        
        list2 = self.merge(lists, mid+1, right)
        return self.mergeTwoLists(list1, list2)

    def mergeTwoLists(self, list1, list2):
        if not list1: return list2
        if not list2: return list1
        if list1.val < list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list2.next, list1)
            return list2