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

• ``````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`

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