My c++ solution 416ms


  • 3
    S

    My code is a typical divide and conquer strategy by comparing lists in pairs recursively, that's all.
    Hope it would be helpful.

    class Solution 
    {
    public:
    ListNode* mergeKLists(vector<ListNode*>& lists){
    if (lists.size() == 0)
    {
        return NULL;
    }
    if (lists.size() == 1)
    {
        return lists[0];
    }
    vector<ListNode*> temp;
    int size = lists.size();
    for (int i = 0; i < size -1; i += 2)
    {
        temp.push_back(splitCompare(lists[i], lists[i+1]));
    }
    if (size % 2 != 0)
    {
        temp.push_back(lists[size - 1]);
    }
    lists[0] = mergeKLists(temp);
    return lists[0];
    }
    ListNode* splitCompare(ListNode* a, ListNode* b)
    {
    if (!a && !b)
    {
        return NULL;
    }
    else if (!a)
    {
        return b;
    }
    else if (!b)
    {
        return a;
    }
    ListNode *result, *temp;
    ListNode *cur1, *cur2;
    cur1 = a;
    cur2 = b;
    if (a->val < b->val)
    {
        result = temp = a;
        cur1 = cur1->next;
    }
    else
    {
        result = temp = b;
        cur2 = cur2->next;
    }
    while (cur1 && cur2)
    {
        if (cur1->val < cur2->val)
        {
            temp->next = cur1;
            cur1 = cur1->next;
        }
        else
        {
            temp->next = cur2;
            cur2 = cur2->next;
        }
        temp = temp->next;
    }
    while (cur1)
    {
        temp->next = cur1;
        cur1 = cur1->next;
        temp = temp->next;
    }
    while (cur2)
    {
        temp->next = cur2;
        cur2 = cur2->next;
        temp = temp->next;
    }
    return result;
    }
    };

Log in to reply
 

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