排序链表（归并排序）

148. 排序链表 - 力扣（LeetCode） 

以O(nlogn)时间复杂度， O(1)空间复杂度 排序链表

涉及知识点： 

• 找到链表的中间节点     2095. 删除链表的中间节点 - 力扣（LeetCode）
• 合并有序链表   21. 合并两个有序链表 - 力扣（LeetCode）
• 归并排序     912. 排序数组 - 力扣（LeetCode）

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
private:// 合并有序链表ListNode *mergeList(ListNode *list1, ListNode *list2){ListNode *dummyhead = new ListNode(0);ListNode *cur = dummyhead;while(list1 && list2){if(list1->val <= list2->val){cur->next = list1;list1 = list1->next;}else{cur->next = list2;list2 = list2->next;}cur = cur->next;}cur->next = list1 ? list1 : list2;return dummyhead->next;}// 找到链表的中间节点ListNode *findMid(ListNode *head, ListNode *end){ListNode *fast=head, *slow=head;while(fast!=end && fast->next!=end){slow = slow->next;fast = fast->next->next;}return slow;}// 归并排序ListNode *mergeSort(ListNode *head, ListNode *end){// end_condif(!head) return head;if(head->next == end){head->next = nullptr;return head;} // find midListNode *mid = findMid(head, end);// groupListNode *list_l = mergeSort(head, mid);ListNode *list_r = mergeSort(mid, end);// mergereturn mergeList(list_l, list_r);}
public:// 以O(nlogn)时间复杂度， O(1)空间复杂度 排序链表ListNode *sortList(ListNode *head) {return mergeSort(head, nullptr);}
};