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

• 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 | -> ...
*     +----+    +----+    +----+
*
* 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.
**/

/**
* 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* tail;
if (l1->val < l2->val) {
l1 = l1->next;
} else {
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;
}
``````

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