[leetcode 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.

 

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 <= 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.

문제 풀이:

leetcode.com/problems/merge-two-sorted-lists/

Merge Two Sorted Lists - LeetCode

이 문제의 심화버전이다. 다양한 방법이 있지만 merge sort의 로직을 이용한다.

 

1 divide and conquer 구현

merge sort와 동일.

다만 연결리스트 이기 때문에 굳이 모든 노드를 복사할 필요가 없다. 

 

2. 최대한 적은 횟수로 비교하기 위한 로직이다.

 

 

 

class Solution {
public:
    
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2){
        ListNode* tmp = new ListNode(0);
        
        ListNode* answer = tmp;
        
        while(l1 && l2){
            if(l1->val < l2->val){
                tmp ->next = l1;
                l1 = l1->next;
                tmp = tmp->next;
            }else {
                tmp ->next = l2;
                l2 = l2->next;
                tmp = tmp->next;
            }
        }
        
        if(l1==nullptr){
            tmp->next = l2;
        }
        
        if(l2==nullptr){
            tmp->next = l1;
        }
        
        return answer->next;
    }
    
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int len = lists.size();
        if(len == 0){
            return nullptr;
        }
        int idx = 1;
        while(idx < len){
            for(int i=0; i+idx<len; i = i+ idx*2){
                lists[i] = mergeTwoLists(lists[i], lists[i+idx]);
            }
            idx *=2;
        }
        return lists[0];
    }
};