23. Merge k Sorted Lists

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.

My Answer 1: Time Limit Exceeded (11 / 133 test cases passed.)

# 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[ListNode]) -> ListNode:
        # 비어있으면 None 리턴
        if len(lists) == 0:
            return None
        
        # 1 개만 있으면 그대로 ListNode 리턴
        if len(lists) == 1:
            return lists[0]
        
        # 비어있는 lists 원소들 pop
        i = 0
        j = 0
        while i != len(lists):
            if lists[j] is None:
                lists.pop(j)
            else:
                j += 1
            i += 1
        
        if len(lists) == 0:
            return None
        if len(lists) == 1:
            return lists[0]
        
        # result ListNode 생성
        result = ListNode(lists[0].val, None)
        head = result
        lists[0] = lists[0].next
        
        while True:
            cnt = 0
            ifsame = 0
            
            # 현재 result 값과 같거나 작은 원소가 있는지 먼저 확인
            # cnt 로 None 의 개수를 셈
            for j in range(len(lists)):
                if lists[j] == None:
                    cnt += 1
                    continue
                if result.val == lists[j].val:
                    result.next = ListNode(lists[j].val, None)
                    result = result.next
                    lists[j] = lists[j].next if lists[j].next != None else None
                    ifsame = 1
                    break
                if result.val > lists[j].val:
                    head = ListNode(lists[j].val, head)
                    lists[j] = lists[j].next if lists[j].next != None else None
                    ifsame = 1
                    break
            
            # 첫번째 반복문에서 같거나 작은 값을 채워준 후 +1 값 확인... => 꼭 1 씩 증가하는게 아님
            if not ifsame:
                for j in range(len(lists)):
                    if lists[j] == None:
                        continue
                    if result.val + 1 == lists[j].val:
                        result.next = ListNode(lists[j].val, None)
                        result = result.next
                        lists[j] = lists[j].next if lists[j].next != None else None
                        break
            
            # cnt 가 len(lists) - 1 이 되면 전부 None 이므로 while 문을 나감
            if cnt == len(lists):
                break
        
        return head

최대한 링크드 리스트 이용해서 하려고 했다...
지저분하지만.. 원소들이 무조건 연속된 숫자인줄 알고 짰음

Approach 1: Brute Force

Solution 1: Runtime: 88 ms - 97.88% / Memory Usage: 18.3 MB - 34.53%

# 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[ListNode]) -> ListNode:
        self.nodes = []
        head = point = ListNode(0)
        for l in lists:
            while l:
                self.nodes.append(l.val)
                l = l.next
        for x in sorted(self.nodes):
            point.next = ListNode(x)
            point = point.next
        return head.next

...73 줄짜리 타임리밋 쓰다가 17 줄의 솔루션을 봤을 때의 내 기분을 서술하시오.(5점)

그냥 무작정 nodes 리스트에 넣은 후에 sort 해서 ListNode 를 새로 만들어주는 것이다.

Solution 2: Runtime: 92 ms - 93.66% / Memory Usage: 18 MB - 49.08%

# 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[ListNode]) -> ListNode:
        h = []
        head = tail = ListNode(0)
        for i in range(len(lists)):
            if lists[i]:
                heapq.heappush(h, (lists[i].val, i, lists[i]))

        while h:
            node = heapq.heappop(h)
            node = node[2]
            tail.next = node
            tail = tail.next
            if node.next:
                i+=1
                heapq.heappush(h, (node.next.val, i, node.next))

        return head.next

힙 h 에 [val 값, 인덱스, lists[i] 노드] 의 형식으로 모두 넣어줌

• 최소 힙(min heap) 형태로 저장되므로 알아서 정렬됨

while 문 돌려서 하나씩 pop 한 다음 tail.next 에 붙여주고
다음 노드가 있으면 새로 heap 에 push 해준다

Priority Queue 랑 비슷한 거 같기도...?

좋은 문제 같음