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;
if (!head)
return;
if (!head->next) {
*a = head;
return;
}
slow = head;
fast = head->next;
while (fast) {
fast = fast->next;
if (fast) {
slow = slow->next;
fast = fast->next;
}
}
*a = head;
*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;
}
}
void mergeSort(ListNode **phead) {
ListNode *a, *b;
ListNode *head = *phead;
// 0 or 1 element
if (!head || !head->next)
return;
breakList(head, &a, &b);
mergeSort(&a);
mergeSort(&b);
*phead = doMerge(a, b);
}
public:
ListNode *sortList(ListNode *head) {
mergeSort(&head);
return head;
}
};
```