# My recursive Merge sort solution

• BreakList use a "fast slow pointer to find the middle of a single list. The idea is pretty simple, every time, fast pointer advance twice, slow pointer advance only 1. ratio is 1/2.
Once the list was split at the middle, then just recursively call mergeSort.
once it get sorted. then just recursively merge two sorted list. I suggest do this one first(merge two sorted lists) https://oj.leetcode.com/problems/merge-two-sorted-lists, if you don't understand this solution.

``````   class Solution {
void breakList(ListNode *head, ListNode **a, ListNode **b) {
*a = *b = NULL;
ListNode *fast, *slow;

return;
return;
}
while (fast) {
fast = fast->next;
if (fast) {
slow = slow->next;
fast = fast->next;
}
}
*b = slow->next;
slow->next = NULL;
}

ListNode *doMerge(ListNode *a, ListNode *b) {
if (!a)
return b;
if (!b)
return a;

if (a->val < b->val) {
a->next = doMerge(a->next, b);
return a;
} else {
b->next = doMerge(b->next, a);
return b;
}
}
ListNode *a, *b;

// 0 or 1 element
return;
mergeSort(&a);
mergeSort(&b);