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;
}
```