148 排序链表

148. 排序链表
要求：时间复杂度 O(NlogN)， 空间O(1)
采用归并排序
我们使用快慢指针 来定位单链表中间的位置

// 快慢指针 + 归并排序 Nlog(N)
    ListNode* sortList(ListNode* head) {
        if(head == NULL || head->next == NULL){
            return head;
        }
        // 使用快慢指针，获取单链表中间的位置
        ListNode *mid=head, *fast=head->next;
        while(true){
            if(fast->next == NULL){
                break;
            }
            fast = fast->next; 
            if(fast->next == NULL){
                break;
            }
            fast = fast->next;
            mid = mid->next;   
        }
        ListNode* second = mid->next;
        mid->next = NULL;
        return mergeTwoOrderedList(sortList(head), sortList(second));
    }
    // 递归合并
    ListNode* mergeTwoOrderedList(ListNode* l1, ListNode* l2){
        if(l1==NULL){
            return l2;
        }
        if(l2==NULL){
            return l1;
        }
        if(l1->val <l2->val){
           l1->next=mergeTwoOrderedList(l1->next, l2);
           return l1;
        }else{
           l2->next=mergeTwoOrderedList(l1, l2->next);
           return l2;
        }
    }