9ms in C (O(n log n) runtime, O(1) space complexity)


  • 0
    N

    You can imagine the input as an intermediate step during a mergesort. A rough explanation is in the comments.

    /**
     * MERGING TWO LISTS
     * ##################
     * 
     * Given two lists L1 and L2 and an unititalized list L'
     * 
     *     +----+    +----+    +----+    
     * L1: | x1 | -> | x2 | -> | x4 | -> ...
     *     +----+    +----+    +----+    
     *     +----+    +----+    +----+    
     * L2: | x3 | -> | x5 | -> | x6 | -> ...
     *     +----+    +----+    +----+    
     * 
     * If the head of L1 is less than the head of L2, then add the head
     * of L1 to L' and then advance L1. Do the opposite otherwise.
     * Repeat until L1 and L2 are empty.
     * 
     *     +----+    +----+    +----+    +----+    +----+    +----+    
     * L': | x1 | -> | x2 | -> | x3 | -> | x4 | -> | x5 | -> | x6 |
     *     +----+    +----+    +----+    +----+    +----+    +----+    
     * 
     * MERGING K LISTS
     * ###############
     * 
     * Given an array L of size n that contains lists L1, L2, L3, ... Ln
     * 
     *    +----+----+----+----+     +------+----+
     * L: | L1 | L2 | L3 | L4 | ... | Ln-1 | Ln |
     *    +----+----+----+----+     +------+----+
     * 
     * Iterate from left to right and merge together every pair of
     * lists that are found. After a list is merged, store the
     * resulting head in the array at half the distance traveled.
     * If n is odd, then skip the merge on the last list and instead
     * store it in L at n / 2.
     * 
     * So if L_x_y' is the merged result of Lx and Ly, then L would
     * look like the following after iterating:
     * 
     *    +--------+--------+--------+     +----------+---+---+     +---+
     * L: | L_1_2' | L_3_4' | L_5_6' | ... | L_n-1_n' | X | X | ... | X |
     *    +--------+--------+--------+     +----------+---+---+     +---+
     * Where X represents now-irrelevant data.
     * 
     * Now recursivley repeat the algorithm on the new half-list until one
     * list remains.
     **/ 
    
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
     
    struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
        // Repeat until there is only one (or zero) list in the array
        while (listsSize > 1) {
            bool odd = listsSize % 2;
            listsSize -= odd;
    
            // Iterate through each pair of array indices
            for (int i = 0; i < listsSize; i+=2) {
                struct ListNode* l1 = *(lists+i);
                struct ListNode* l2 = *(lists+i+1);
    
                // Preliminary empty list check
                if (l1 == 0) { *(lists + (i >> 1)) = l2; continue; }
                if (l2 == 0) { *(lists + (i >> 1)) = l1; continue; }
                struct ListNode* head;
                struct ListNode* tail;
                if (l1->val < l2->val) {
                    head = tail = l1;
                    l1 = l1->next;
                } else {
                    head = tail = l2;
                    l2 = l2->next;
                }
                // If both lists contain more than one element, then merge
                while (true) {
                    if (l1 == 0) { tail->next = l2; break; }
                    if (l2 == 0) { tail->next = l1; break; }
                    if (l1->val < l2->val) {
                        tail->next = l1;
                        l1 = l1->next;
                    } else {
                        tail->next = l2;
                        l2 = l2->next;
                    }
                    tail = tail->next;
                }
                *(lists + (i >> 1)) = head;
            }
            // Skip merging on the last list if the list size is odd
            if (odd) *(lists + (listsSize >> 1)) = *(lists + listsSize);
            // After all lists are merged and stored, resize the list and repeat
            listsSize = (listsSize >> 1) + odd;
        }
        return *lists;
    }
    

Log in to reply
 

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