Merge k Sorted Lists[H,Linked List,Divide and Conquer,Heap ,(Priority Queue)Merge Sort]

https://leetcode.com/problems/merge-k-sorted-lists/description/

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.

 

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

 

Constraints:

• k == lists.length
• 0 <= k <= 104
• 0 <= lists[i].length <= 500
• -104 <= lists[i][j] <= 104
• lists[i] is sorted in ascending order.
• The sum of lists[i].length will not exceed 104.

처음으로 접하는 H(Hard) 난이도의 문제

하지만 걱정마라. 어차피 Medium, Easy 난이도 문제도 다 어려웠었다..!

 

1. Python

# 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]:
        if not lists : return

        temp = None
        for x in lists:
            if not temp:
                temp = x
                continue
            elif not x:
                continue
            else : # There are both temp & x
                dummy = ListNode(-99)
                curr = dummy
                while temp and x:
                    if temp.val < x.val:
                        curr.next = temp
                        temp = temp.next
                        curr = curr.next
                    else:
                        curr.next = x
                        x = x.next
                        curr = curr.next
                if temp:
                    curr.next = temp
                else: curr.next = x
                temp = dummy.next
        return temp

 

 

List를 이용해서도 풀어봤는데, O(N^2)이라는 엄청난 시간이 소요된다.

# 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]:
        if not lists : return
        
        lst = []
        for x in lists:
            curr = x
            while curr :
                lst.append(curr)
                curr = curr.next
                
        if not lst:
            return

        # list sorting (Selection Sort)
        for i in range(len(lst)):
            minidx = i
            for j in range(i+1,len(lst)):
                if lst[minidx].val > lst[j].val:
                    minidx = j
            lst[minidx],lst[i] = lst[i],lst[minidx]
        
        for i in range(len(lst)-1):
            lst[i].next = lst[i+1]
        lst[-1].next = None
        return lst[0]

 

문제 Topic에 Heap이 있는대도 꿋꿋이 linked list끼리 어거지로 이었다. Heap 풀이도 함 봐야지

 

Heap으로 풀면 O(N log k , k 는 list 개수 )

heapq 라는 것을 import 해줘야 하고, 기본적으로 min-priority 구조이다.

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        heap = [] # for heapq
        import heapq   
        # Heap initialize
        for i, node in enumerate(lists):
            if node:
                heapq.heappush(heap,(node.val,i,node))
    
        # dummy for merge
        dummy = ListNode(0)
        temp = dummy

        while heap:
            val, i, node = heapq.heappop(heap)
            temp.next = ListNode(val)
            temp = temp.next
            if node.next:
                heapq.heappush(heap,(node.next.val,i,node.next))
        
        return dummy.next

 

이번엔 내가 아직 정복하지 못한, Merge sort로 풀어보기.

Insertion / Selection sort는 참 정겨운데 이놈은 Recursive를 써야해서 이해가 어렵다 ㅠㅠ

 

그래도 오다 가다 종종 만날 친구니까 함 집고 넘어가보자.

 

# 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]:
        if not lists: return
        if len(lists) == 1 : return lists.pop()

        # Divide
        mid = len(lists)//2
        left = self.mergeKLists(lists[:mid])
        right = self.mergeKLists(lists[mid:])

        # Conquer
        return self.merge(left,right)

    def merge(self,l1,l2):
        dummy = ListNode(0)
        curr = dummy

        while l1 and l2 :
            if l1.val < l2.val:
                curr.next = l1
                l1 = l1.next
                curr = curr.next
            else:
                curr.next = l2
                l2 = l2.next
                curr = curr.next
        if l1:
            curr.next = l1
        else:
            curr.next = l2
        return dummy.next

 

 

2. C

비슷한 맥락으로 풀었다. C로는 무조건 pointer 등등의  방법으로만 문제를 풀 수 있을 거 같다.

container가 array뿐이니 heap을 사용하는 등의 방법은 부적절할듯

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
    if(listsSize==0) return NULL;
    // solve it w/o any function
    struct ListNode* ans = NULL;

    for(int i=0; i<listsSize; i++){
        struct ListNode* curr = lists[i];
        if(!curr) continue;
        else if(!ans){
            ans = curr;
            continue;
        }
        else{ // There are both ans & curr
            struct ListNode dummy;
            struct ListNode* temp = &dummy;
            while(ans && curr){
                if(ans->val < curr->val){
                    temp->next = ans;
                    ans = ans->next;
                    temp = temp->next;
                }else{
                    temp->next = curr;
                    curr = curr->next;
                    temp = temp->next;                 
                }
            }
            temp->next = curr ? curr : ans;
            ans = dummy.next;
        }
    }
    return ans;
}

 

- Merge Sort로 해보기

 

좀 고차원적인 merge sort Recursive 방법이다.

 struct ListNode* merge(struct ListNode* l, struct ListNode* r){
    if(!l) return r;
    if(!r) return l;

    if(l->val < r->val){
        l->next = merge(l->next,r);
        return l;
    }else{
        r->next = merge(l,r->next);
        return r;
    }
}
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
    if(listsSize == 0 ) return NULL;
    if(listsSize == 1 ) return lists[0];

    int mid = listsSize / 2 ;
    // Here is the KEY POINT!!
    struct ListNode* left = mergeKLists(lists,mid);
    struct ListNode* right = mergeKLists(lists+mid,listsSize-mid);

    return merge(left,right);
}

 

3. C++

 

heap으로 풀기

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        auto comp = [](ListNode* a,ListNode* b){
            if(!a) return false;
            if(!b) return true;
            return a->val > b->val;
        };
        // min - heap
        priority_queue<ListNode*,vector<ListNode*>,decltype(comp)> minq(comp);

        for(auto x : lists){
            minq.push(x);
        }

        ListNode dummy;
        ListNode* temp = &dummy;

        while(!minq.empty()){
            ListNode* curr = minq.top();
            minq.pop();

            if(!curr) continue;
            temp -> next = curr;
            temp = temp->next;

            if(curr->next){
                minq.push(curr->next);
            }
        }
        temp -> next = nullptr;
        return dummy.next;
    }
};