[LeetCode][Python3] 23. Merge k Sorted Lists
2019. 4. 7. 23:16 |
프로그래밍/LeetCode
Problem :
https://leetcode.com/problems/merge-k-sorted-lists/
My Solution :
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
if lists:
if len(lists) == 1:
return lists[0]
mid = len(lists) // 2
left = self.mergeKLists(lists[:mid])
right = self.mergeKLists(lists[mid:])
return self.merge(left, right)
def merge(self, left, right):
current = dummy = ListNode(0)
while left and right:
if left.val < right.val:
current.next = left
left = left.next
else:
current.next = right
right = right.next
current = current.next
current.next = left or right
return dummy.next
Comment :
예전에 풀었던 병합정렬 문제 답안을 약간만 수정하였다. 한번 풀어놓은 문제의 답안이 Template처럼 계속 쓰이네...
2019/04/04 - [프로그래밍/LeetCode] - [LeetCode][Python3] 148. Sort List
2018/09/11 - [프로그래밍/LeetCode] - [LeetCode][Python3] 21. Merge Two Sorted Lists
아래는 병합 정렬 말고 dictionary를 활용하여 버킷 정렬 비슷하게 접근해 보았는데 속도가 훨씬 개선되었다.
My Solution 2 :
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
bucket = {}
for node in lists:
while node:
head, tail = bucket.get(node.val, [None, None])
if not head:
bucket[node.val] = [node, node]
else:
tail.next = node
bucket[node.val][1] = node
node = node.next
vals = sorted(bucket)
for i in range(len(vals)-1):
bucket[vals[i]][1].next = bucket[vals[i+1]][0]
if bucket:
bucket[vals[-1]][1].next = None
return bucket[vals[0]][0]
'프로그래밍 > LeetCode' 카테고리의 다른 글
[LeetCode][Python3] 150. Evaluate Reverse Polish Notation (0) | 2019.04.10 |
---|---|
[LeetCode][Python3] 33. Search in Rotated Sorted Array (0) | 2019.04.10 |
[LeetCode][Python3] 227. Basic Calculator II (0) | 2019.04.09 |
[LeetCode][Python3] 134. Gas Station (0) | 2019.04.08 |
[LeetCode][Python3] 210. Course Schedule II (0) | 2019.04.05 |
[LeetCode][Python3] 148. Sort List (1) | 2019.04.04 |
[LeetCode][Python3] 139. Word Break (0) | 2019.04.03 |
[LeetCode][Python3] 56. Merge Intervals (0) | 2019.04.03 |
최근에 달린 댓글 최근에 달린 댓글