❗️[LEET CODE] 23. Merge k Sorted Lists ( k개 정렬 리스트 병합)

# Problem

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.     Constraints: k == lists.length 0 <= k <= 10^4 0 <= lists[i].length <= 500 -10^4 <= lists[i][j] <= 10^4 lists[i] is sorted in ascending order. The sum of lists[i].length won't exceed 10^4.

 

# My Answer

class Solution:
    def _sort(self,l1,l2): # 리스트 2개를 정렬하는 함수
        if l1 and l2:
            if l1.val>l2.val :
                l1,l2 = l2,l1
            head = node = l1
            l1 = l1.next
        elif l1 is not None: 
            return l1
        else:
            return l2
        while l1 and l2:            
            if l1.val>l2.val :
                l1,l2 = l2,l1
                node.next = l1
            l1 = l1.next
            node = node.next
        if l1 is None:
            node.next = l2            
        return head

    def mergeKLists(self, lists: List[ListNode])->ListNode:
        if lists==[]:
            return 
        elif len(lists)==1 and lists[0]is None:
            return
        elif len(lists)<=1:
            return lists[0]
        a = lists[0]
        
        for ll in lists[1:]: # 앞에서 부터 2개씩 정렬
            a = self._sort(a,ll)
        return a

 

# Solution 1 - 우선순위 큐를 이용한 리스트 병합

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        root = result = ListNode(None)
        heap = []

        # 각 연결 리스트의 루트를 힙에 저장
        for i in range(len(lists)):
            if lists[i]:
                heapq.heappush(heap, (lists[i].val, i, lists[i]))
		
        print(heap)
        # [(1, 0, ListNode{val: 1, next: ListNode{val: 4, next: ListNode{val: 5, next: None}}}),
        #  (1, 1, ListNode{val: 1, next: ListNode{val: 3, next: ListNode{val: 4, next: None}}}),
        #  (2, 2, ListNode{val: 2, next: ListNode{val: 6, next: None}})]

        # 힙 추출 이후 다음 노드는 다시 저장
        while heap:
            node = heapq.heappop(heap)
            idx = node[1] # 중복값 구분
            result.next = node[2]

            result = result.next
            if result.next: # 다음 노드 다시 힙에 저장
                heapq.heappush(heap, (result.next.val, idx, result.next))

        return root.next

heapq 모듈 사용

import heapq

---

# heapq 모듈

최소힙 지원 - 값이 작은 순서대로 heappop()

동일한 값은 Error - 중복된 값을 구분할 수 있는 추가 인자 필요 - 위 문제에서는 idx사용

heappush(추가할 힙, 값)