Beautiful solution using D&C in C++ @32ms


  • 1
    class Solution {
    public:
        ListNode* merge2Lists(ListNode* l1, ListNode* l2)
        {
           if(!l1) return l2;
           if(!l2) return l1;
           if(l1->val <= l2->val)
           {
               l1->next = merge2Lists(l1->next, l2);
               return l1;
           }
           else
           {
               l2->next = merge2Lists(l2->next, l1);
               return l2;
           }
        }
        ListNode* mergeHelper(vector<ListNode*>& lists, int left, int right)
        {
            if(left == right) return lists[left];
            int pos = (left + right) / 2;
            return merge2Lists(mergeHelper(lists, left, pos), mergeHelper(lists, pos + 1, right));
        }
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            if(lists.empty()) return NULL;
            return mergeHelper(lists, 0, lists.size()-1);
        }
    };

  • 0
    H

    It's just awesome! Amazing algo design!


Log in to reply
 

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