[leetcode] 23. Merge k Sorted Lists

문제 설명

링크
k 개의 정렬된 연결리스트를 하나로 정렬하기

접근 1 - k개의 ptr 이용

• 연결리스트들을 순회하며 최소값을 찾고
• 이를 head 에 연결
• 시간이 오래 소요됨 (O(kn))

코드 1

    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        k = len(lists)
        res = head = None

        while any([h != None for h in lists]):
            minIdx = 0
            minVal = float('inf')
            for idx in range(k):
                if lists[idx] and lists[idx].val < minVal:
                    minIdx = idx
                    minVal = lists[idx].val

            if not res:
                res = head = lists[minIdx]
            else:
                head.next = lists[minIdx]
                head = head.next
            lists[minIdx] = lists[minIdx].next
  

        return res

접근 2 - Merge Sort

• divide and conquer 이용
• 시간 통과!

코드 2

    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        k = len(lists)       
        
        if k > 1:
            list1 = self.mergeKLists(lists[:k//2])
            list2 = self.mergeKLists(lists[k//2:])
            return self.merge(list1, list2)
        if k == 1:
            return lists[0]
        if k == 0:
            return None

            
    def merge(self, list1, list2) -> Optional[ListNode]:
        if not list1:
            return list2
        if not list2:
            return list1
                
        head = ptr = None
        if list1.val <= list2.val:
            head = ptr = list1
            list1 = list1.next
        else:
            head = ptr = list2
            list2 = list2.next
                
        while list1 and list2:
            if list1.val < list2.val:
                ptr.next = list1
                list1 = list1.next
            else:
                ptr.next = list2
                list2 = list2.next
            ptr = ptr.next
        if list1:
            ptr.next = list1
        if list2:
            ptr.next = list2
        return head