# My recursive and iterative versions C++ (60ms)

• Both are based on divide-and-conquer. divide the list into two, sort each of them and merge. Below is the recursive version. Due to the recursion, it needs O(logN) space, not constant.

``````class Solution {
private:
ListNode *split(ListNode *head) //split the list into two
{
ListNode *fast, *slow;
while(fast->next && fast->next->next)
{
fast = fast->next->next;
slow = slow->next;
}
fast = slow->next;
slow->next = nullptr;
return fast;
}
{
ListNode dummy(0);

{
}
return dummy.next;
}

public:

}
};
``````

Then to achieve O(1) space, we can implement the above recursive version in a bottom-up iterative way.
We divide the list into sub-lists with the length of len (len starting with 1) and then we merge-sort two consecutive sub-lists. Then we double len and merge-sort two consecutive sub-lists, which are the resulting sublists from the previous merge-sort Then we continue...

``````class Solution {
public:

int len=1, merge, i;

do{
merge =0; // number of mergesort it does in the current iteration
do
{
++merge;
for(i=0;i<len && tail1->next;++i) tail1 = tail1->next; // get the first half sub-list to be merged
if(i<len || !tail1->next) break; // if it reaches the end, jump out the inner loop
tail2 = newHead;  // find the second half sub-list
for(i=0;i<len && tail2;++i) tail2 = tail2->next;
tail1->next = tail2;  // note set tail1s next to tail2 to ensure the last node of the resulting list will still link to the rest of the list.
{