[leetcode] 23. Merge k Sorted Lists

문제

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

풀이

우리는 Merge Two Sorted Lists를 알고있다고 가정하자.

그렇다면 분할정복을 이용해서 문제를 해결할 수 있다.

list를 절반으로 나눠서 각각의 Merge k/2 Sorted Lists를 구한 다음, 이 두 list를 Merge Two Sorted Lists로 합치면 끝.

 

시간복잡도를 $T(list)$이라 한다면 $T(list)=T(l)+T(r)+O(|N|)$이므로 $T(list)=O(|N|logk)$이다.

(여기서 |N|은 총 노드의 수, k는 list의 원소의 수)

 

Time Complexity : $O(|N|logk)$

 

코드

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution{
private:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode * ans=new ListNode(0);
        ListNode * it =ans;
        for(ListNode* i1=l1, *i2=l2; i1 || i2;it=it->next)
        {
            if(i1==NULL)
            {
                it->next=i2;
                i2=i2->next;
            }
            else if(i2==NULL)
            {
                it->next=i1;
                i1=i1->next;
            }
            else if(i1->val>i2->val)
            {
                it->next=i2;
                i2=i2->next;
            }
            else
            {
                it->next=i1;
                i1=i1->next;
            }
        }
        return ans->next;
    }
    ListNode* merge(int l, int r, vector<ListNode*>& lists)
    {
        if(l==r) return NULL;
        if(l+1==r) return lists[l];
        int mid=(l+r)/2;
        return mergeTwoLists(merge(l,mid,lists), merge(mid,r,lists));
    }
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(0,lists.size(),lists);
    }
};