탑 핫 100번.
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
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