문제

• 각각이 오름차순으로 정렬된 linked list들 lists
• 정렬된 하나의 linked list로 만들기

풀이

• heap 라이브러리 이용해서 해보면 되지 않을까...?
  • 같은 priority를 갖을 때, 비교가 안됨..
• defaultdict(list) 이용해서 해볼까..

예외처리

• lists가 []인 경우
• lists가 [[]]인 경우

from collections import defaultdict
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        dic = defaultdict(list)
        for thisNode in lists:
            if thisNode:
                # lists = [[]]일 때 걸러내기
                while thisNode.next is not None:
                    dic[thisNode.val].append(thisNode)
                    thisNode = thisNode.next
                dic[thisNode.val].append(thisNode) # 마지막 node
        # dict에서 빼서 정렬된 리스트로 만들기
        sortedList = []
        for key in sorted(dic.keys()):
            for el in dic[key]:    
                sortedList.append(el)
        # 리스트에 담긴 순으로 노드 연결
        headNode = None
        for ind, el in enumerate(sortedList):
            if ind != len(sortedList)-1:
                el.next = sortedList[ind+1]
            if ind == 0:
                headNode = el
        return headNode
                

결과

두 가지 예외처리 경우 때문에 조금 해맸다.
리트코드에서는 항상 이런 None 값을 input으로 테스트하는 것 같은데, 다음부터 미리 예외를 생각하고 코드를 짜야겠다..!