Recursive cpp code


  • 0
    C
    class Solution {
    public:
        ListNode* mergeHelper(const vector<ListNode*>& lists, int start, int end)
        {
            if(start == end-1) return lists[start];
            if(start == end) return NULL;
            
            int mid = start + (end-start)/2;
            ListNode* l = mergeHelper(lists, start, mid);
            ListNode* r = mergeHelper(lists, mid, end);
            
            ListNode fakeHead(0);
            ListNode *ptr = &fakeHead;
            while(l && r)
            {
                if(l->val < r->val)
                {
                    ptr->next = l;
                    ptr = ptr->next;
                    l = l->next;
                }
                else
                {
                    ptr->next = r;
                    ptr = ptr->next;
                    r = r->next;
                }
            }
            
            if(l) ptr->next = l;
            else ptr->next = r;
            
            return fakeHead.next;
        }
    
        ListNode* mergeKLists(vector<ListNode*>& lists) 
        {
            return mergeHelper(lists, 0, lists.size());
        }
    };

Log in to reply
 

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