leetcode 148. Sort List

148. Sort List

题目描述

代码：

/*** 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 {
public:ListNode* sortList(ListNode* head) {if(head == nullptr)return nullptr;return merge_sort(head,nullptr);}pair<ListNode*,ListNode*> find(ListNode* head){ListNode* fast = head;ListNode* slow = head;ListNode* preslow = nullptr;while(fast&&fast->next){fast = fast->next->next;preslow = slow;slow = slow->next;}if(preslow == nullptr)return {slow,slow};return {preslow,slow};}ListNode* merge_sort(ListNode *head,ListNode* tail){if(head == tail)return head;auto mid_pair = find(head);if(mid_pair.first == mid_pair.second)return head;mid_pair.first->next = nullptr;ListNode* left  = merge_sort(head,mid_pair.first);ListNode* right = merge_sort(mid_pair.second,tail);ListNode* dummy = new ListNode(-1,nullptr);ListNode* pre = dummy;while(left&&right){if(left->val < right->val){pre->next = left;pre = left;left = left->next;}else{pre->next = right;pre = right;right = right->next;}}if(left)pre->next = left;elsepre->next = right;ListNode* newHead = dummy->next;delete dummy;return newHead;}
};