ListNode * merge(ListNode *lhs, ListNode *rhs)
ListNode *head = new ListNode(0);
while (lhs != nullptr || rhs != nullptr)
if (lhs != nullptr && rhs != nullptr)
ListNode ** smallest = lhs->val < rhs->val ? &lhs : &rhs;
*smallest = (*smallest)->next;
cur->next = lhs != nullptr ? lhs : rhs;
ListNode * sortList(ListNode* head)
std::vector<ListNode*> sortedLists;
for (ListNode *i = head; i != nullptr; )
if (i->next != nullptr && i->val > i->next->val)
sortedLists.push_back(helper);
sortedLists.push_back(helper);
int sz = sortedLists.size();
for (int i = 0; i < sz / 2; i++) {
sortedLists[i] = merge(sortedLists[i], sortedLists[j]);
return sz > 0 ? sortedLists[0] : NULL;