Simple C++ solution beats 67%


  • 0
    J
    class Solution {
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            if (lists.size()==0) return nullptr;
            if (lists.size()==1) return lists[0];
            if (lists.size()==2) return mergeTwoLists(lists[0], lists[1]);
            vector<ListNode*> List1(lists.begin(), lists.begin() + (lists.end()-lists.begin()) / 2);
            vector<ListNode*> List2(lists.begin() + (lists.end()-lists.begin()) / 2, lists.end());
            return mergeTwoLists(mergeKLists(List1), 
                mergeKLists(List2));
        }
        
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
            ListNode prehead(0);
            ListNode* p = &prehead;
            while (l1 && l2) {
                if (l1->val < l2->val) {
                    p->next = new ListNode(l1->val);
                    l1 = l1->next;
                }
                else {
                    p->next = new ListNode(l2->val);
                    l2 = l2->next;              
                }
                p = p->next;
            }
            if (!l1) p->next = l2;
            else p->next = l1;
        return prehead.next;
        }
    };

Log in to reply
 

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