148 sort list

O(n log n) time 的要求，可以参与merge sort

寻找中间节点的时候，我们不是需要找到的中间节点的前一个节点，而不是中间节点本身
因此初始化fast的时候提前走一步：
slow = head;
fast = head->next;

之后对slow->next做排序， 然后把前半部末尾设置为NULL，然后进行归并排序。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {

    struct ListNode *dummyhead = malloc(sizeof(struct ListNode));
    dummyhead->next = NULL;
    struct ListNode *lastnode = dummyhead;

    while(1){
        if(l1&&l2){
            if(l1->val < l2->val){
                lastnode->next = l1;
                l1 = l1->next;
                lastnode = lastnode->next;
            }else{
                lastnode->next = l2;
                l2 = l2->next;
                lastnode = lastnode->next;
            }
        }else if(l1){
            lastnode->next = l1;
            break;
        }else if(l2){
            lastnode->next = l2;
            break;
            
        }else
            break;
    }

    struct ListNode * tmp = dummyhead->next;
    free(dummyhead);
    return tmp;

}


//Sort a linked list in O(n log n) time using constant space complexity.

struct ListNode* sortList(struct ListNode* head) {
    if(head == NULL || head->next == NULL)
        return head;
    struct ListNode *slow, *fast;
    struct ListNode *l1, *l2;
    l1 = l2 = NULL;


    slow = head;
    fast = head->next;


    while(fast){
        fast = fast->next;
        if(fast){
            fast = fast->next;
            slow = slow->next;
        }

    }

    //mid is slow 
    if(slow->next)
        l2 = sortList(slow->next);
    slow->next = NULL;
    l1 = sortList(head);
    return mergeTwoLists(l1, l2);
    
}