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;
}
}
