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]