题解 | #单链表的排序#

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */

/*
class Solution {
public:
   ListNode* sortInList(ListNode* head) {
       // write code here
       vector<int> vec;
       ListNode* p=head;
       while(p) {
           vec.push_back(p->val);
           p=p->next;
       }
       sort(vec.begin(),vec.end());
       ListNode* dummy= new ListNode(0);
       p = dummy;
       for(int i=0;i<vec.size();i++) {
           ListNode* tmpNode = new ListNode(vec[i]);
           p->next=tmpNode;
           p=p->next;
       }
       p=nullptr;
       return dummy->next;
   }
};
*/
class Solution {
  public:
    ListNode* sortInList(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
            return head;
        ListNode* slow = head;
        ListNode* fast = head;
        // 使用快慢指针寻找链表的中点
        while(fast && fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        ListNode* tmp = slow->next;
        slow->next = nullptr;
        // 递归左右两边进行排序
        ListNode* left = sortInList(head);
        ListNode* right = sortInList(tmp);
        // 创建新的链表
        ListNode* dummy = new ListNode(0);
        ListNode* h = dummy;
        // 合并 left right两个链表
        while (left && right) {
            if (left->val <= right->val) {
                h->next = left;
                left = left->next;
            } else {
                h->next = right;
                right = right->next;
            }
            h = h->next;
        }
        // 最后添加未对比的链表部分判断左链表是否为空
        h->next = left != nullptr ? left : right;
        return dummy->next;
    }
};