23. 여러 정렬 체인 테이블 결합:https://leetcode-cn.com/problems/merge-k-sorted-lists/

이 문제는 사실 비교적 간단하다. 관건은 퇴적과 분치법을 파악하는 것이다. 분치법을 쓸 때 귀착과 관련된다. 이것은 나의 약점이다. 처음에 쓰지 못했기 때문에 분치법 틀은 참고할 수 있다.

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        return self.helper(0, len(lists), lists)
    #  
    def helper(self, start, end, lists):
        if start == end:
            return lists[start]
        mid = start + (end - start) / 2
        left = self.helper(start, mid, lists)
        right = self.helper(mid+1, end, lists)
        return self.mergeTwoSortLists(left, right)

    def mergeTwoSortLists(self, list1, list2):
        '''
        @description:  
        @param {type} 
                list1: 
                list2: 
        @return: 
                result: 
        @author: zhangzhen20
        '''  
        dummy = listNode(-1)
        cur = dummy
        while list1 and list2:
            if list1.val < list2.val:
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next

        if list1 is None:
            cur.next = list2
        else:
            cur.next = list1

        return dummy.next