Share my 32ms non-recursive divide-and-conquer C++ solution


  • 0
    F
    class Solution {
    public:
        /**
         * @param lists: a list of ListNode
         * @return: The head of one sorted list.
         */
        ListNode *mergeKLists(vector<ListNode *> &lists) {
            if (lists.empty()) {
                return NULL;
            }
            int len = lists.size();
            while (len >= 2) {
                for (int i = 0; i < len / 2; ++i) {
                    lists[i] = mergeTwoLists(lists[i<<1], lists[i<<1|1]);
                }
                if (len % 2 == 0) {
                    len  = len>>1;
                } else {
                    lists[len>>1] = lists[len-1];
                    len = (len>>1) + 1;  // note: the priority of '+' is larger than '>>'
                }
            }
            return lists[0];
        }
        
        ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
            ListNode dummy(0);
            ListNode *cur = &dummy;
            while (l1 && l2) {
                if (l1->val < l2->val) {
                    cur->next = l1;
                    l1 = l1->next;
                } else {
                    cur->next = l2;
                    l2 = l2->next;
                }
                cur = cur->next;
            }
            cur->next = l1? l1:l2;
            return dummy.next;
        }
    };
    

    The shift operation is used for efficiency (not necessary). len<<1 means len * 2 and len<<1|1 means len*2 + 1, similarly, len>>1 equals len / 2


Log in to reply
 

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