Simple C++ solution


  • 0
    X

    share my straightforward c++ solution. Merge the lists two by two. If there is anythingwrong, please figure it out. Hoping to learn more about them.

      class Solution {
        private:
            ListNode* merge2list(ListNode* a, ListNode* b){
                ListNode fakeNode(0);
                ListNode *p = &fakeNode;
                while(a != nullptr && b != nullptr){
                    if(a->val < b->val){
                        p->next = a;
                        a = a->next;
                    }
                    else{
                        p->next = b;
                        b = b->next;
                    }
                    p = p->next;
                }
                if(a != nullptr)
                    p->next = a;
                if(b != nullptr)
                    p->next = b;
                return fakeNode.next;
            }
        public:
            ListNode* mergeKLists(vector<ListNode*>& lists) {
                if(lists.empty())
                    return nullptr;
                if(lists.size()<2)
                    return lists.back();
                vector<ListNode*>   merged;
                while(lists.size()>1){
                    merged.clear();
                    if(lists.size()%2 == 0){
                        for(int i = 0; i < lists.size()/2 ; i++){
                            merged.push_back(merge2list(lists[i], lists[lists.size() - 1 - i]));
                        }
                    }
                    else{
                        for(int i = 0; i < lists.size()/2 ; i++){
                            merged.push_back(merge2list(lists[i], lists[lists.size() - 1 - i]));
                        }
                        merged.push_back(lists[lists.size()/2]);
                    }
                    swap(merged, lists);
                }
                return lists.back();
            }
        };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.