[LeetCode]023-Merge K Sorted Lists

テーマ:Merge k sorted linked lists and return it as one sorted list.Analyze and describe its complexity.
Solution(1):初期のアプローチは,再帰を用いるが,実際には2つの統合でアルゴリズム設計が劣る.タイムアウト.複雑度はO(n^2);

ListNode* mergeKLists(vector<ListNode*>& lists) {
        int n =lists.size();
        if(n == 0)
            return NULL;
        merge_all_Lists(lists,n);
        return lists[0];
    }

    void merge_all_Lists(vector<ListNode*>& lists,int k) 
    {
        ListNode* r_list = new ListNode(NULL);
        ListNode* head = r_list;

        if(k == 0 || k == 1)
            return ;
        else if(k==2)
        {
            ListNode* l1 = lists[0];
            ListNode* l2 = lists[1];
            if(l1 == NULL)
            {
                lists.erase(lists.begin());
                return ;
            }
            if(l2 == NULL)
            {
                lists.erase(lists.begin()+1);
                return ;
            }
            while(l1 != NULL && l2 != NULL)
            {
                if(l1->val < l2->val)
                {
                    r_list->val = l1->val;
                    l1 = l1->next;
                }
                else
                {
                    r_list->val = l2->val;
                    l2 = l2->next;
                }
                if(l1 != NULL && l2 != NULL)
                {
                    r_list->next = new ListNode(NULL);
                    r_list = r_list->next;
                }
            }
            while(l1 != NULL)
            {
                r_list->next = new ListNode(NULL);
                r_list = r_list->next;

                r_list->val = l1->val;
                l1 = l1->next;
            }
            while(l2 != NULL)
            {
                r_list->next = new ListNode(NULL);
                r_list = r_list->next;

                r_list->val = l2->val;
                l2 = l2->next;
            }
            lists.erase(lists.begin());
            lists.erase(lists.begin());
            lists.insert(lists.begin(),head);
            return;
        }
        else
        {
            while(lists.size() >1)
                merge_all_Lists(lists,k-1); 
        }
    }

Solution(2):修正して分治法で行うと効率が向上し,複雑度はO(nlogn)となる.

    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        int n = lists.size();
        if(n == 0)
            return NULL;
        return merge_lists(lists,0,n-1);
    }

    ListNode* merge_lists(vector<ListNode*> &lists,int low,int high)
    {
        if(low<high)
        {
            int mid = (low+high)/2;
            return mergeTwoLists(merge_lists(lists,low,mid),merge_lists(lists,mid+1,high));
        }
        return lists[low];
    }

    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
    {
        if(l1 == NULL)
            return l2;
        if(l2 == NULL)
            return l1;
        ListNode * t1 = l1;
        ListNode * t2 = l2;

        ListNode * l3 = new ListNode(NULL);

        ListNode *head = l3;
        while(t1!=NULL && t2!=NULL)
        {
            if(t1->val < t2->val)
            {
                l3->val = t1->val;
                t1 = t1->next;
            }
            else
            {
                l3->val = t2->val;
                t2 = t2->next;
            }
            if(t1 != NULL && t2 !=NULL)
            {
                l3->next = new ListNode(NULL);
                l3 = l3->next;
            }
        }

        while(t1!=NULL)
        {
            l3->next = new ListNode(NULL);
            l3 = l3->next;
            l3->val = t1->val;

            t1 = t1->next;
        }

        while(t2!=NULL)
        {
            l3->next = new ListNode(NULL);
            l3 = l3->next;
            l3->val = t2->val;

            t2 = t2->next;
        }
        return head;
    }