Share my C++ solution,easy to understand


  • 1
    V
    class Solution {
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            int n = lists.size();
            if (n == 0)
                return NULL;
            if (n == 1)
                return lists[0];
                
            return recursionMerge(lists, 0, n-1);
        }
        
        ListNode* recursionMerge(vector<ListNode*>& lists, int start, int end)
        {
            if (start == end)
                return lists[start];
            
            int mid = start + (end - start) / 2;
            
            ListNode *l1 = recursionMerge(lists, start, mid);
            ListNode *l2 = recursionMerge(lists, mid+1, end);
            
            ListNode head(0); 
            ListNode *cur = &head;
            
            while (l1 && l2)
            {
                if (l1->val <= l2->val)
                {
                    cur->next = l1;
                    l1 = l1->next;
                }
                else
                {
                    cur->next = l2;
                    l2 = l2->next;
                }
                
                cur = cur->next;
            }
            
            if (l1 != NULL)
                cur->next = l1;
            else
                cur->next = l2;
                
            return head.next;
        }
    };

Log in to reply
 

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