# 148-Sort List
###### tags: `Medium`
## Question
https://leetcode.com/problems/sort-list/
## Key
- 因為題目要求sorting complexity要是O(nlogn)，所以用Merge sort
- 如何找到middle point
- 如何進行merge sort在linked list中(遞迴)
## Reference
## Solution

ListNode* sortList(ListNode* head) {
     if(head == NULL || head->next == NULL) return head;

     ListNode *slow = head;
     ListNode *fast = head->next;
    // find the middle point of the list
     while(fast != NULL && fast->next != NULL){
         slow = slow->next;
         fast = fast->next->next;
     }
    //partition the list into left list and right list
     ListNode *middleNode = slow->next;
     slow->next = NULL;
    //remember starting from head and middle point
     ListNode *left = sortList(head);
     ListNode *right = sortList(middleNode);
     return mergeSortList(left, right);
}

ListNode *mergeSortList(ListNode *left, ListNode *right){
    ListNode *dummy = new ListNode(-1);
    ListNode *cur = dummy;

    while(left != NULL && right != NULL){
        if(left->val < right->val){
             cur->next = left;
             left = left->next;
        }else{
             cur->next = right;
             right = right->next;
        }
        cur = cur->next;
    }

    while(left != NULL){
        cur->next = left;
        cur = cur->next;
        left = left->next;
    }

    while(right != NULL){
        cur->next = right;
        cur = cur->next;
        right = right->next;
    }

    return dummy->next;
}