题解 | #单链表的排序#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <memory>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    ListNode* sortInList(ListNode* head) {
        // write code here
        if(!head||!head->next)//如果链表为空或链表只有一个元素返回链表
        {
            return head;
        }
       //创建快慢指针找中间节点
       ListNode* fast=head;
       ListNode* slow=head;
       //循环结束条件为快指针的next和next的next不为空
       while(fast->next!=nullptr&&fast->next->next!=nullptr){
        fast=fast->next->next;
        slow=slow->next;
       }
       //断开中间节点
       ListNode* mid=slow->next;
       slow->next=nullptr;
       //在对子序列递归做断开中间的步骤
        ListNode* left=sortInList(head);
        ListNode* right=sortInList(mid);
        //合并子序列
        return hebing(left,right);
    }
    
        ListNode* hebing(ListNode* left, ListNode* right){
        //动态创建头节点
        ListNode* head=new ListNode(0);
        //创建可以移动的头指针
        ListNode* tem=head;
         if (!left) { // 如果左子链表为空，则直接返回右子链表
         return right;
        } else if (!right) { // 同理，如果右子链表为空，则返回左子链表
        return left;
    }
    //循环条件循环直到有一边为空
    while (left!=nullptr&&right!=nullptr) {
        //如果左比右小则把左的节点连接到tem后
        if(left->val<right->val){
            tem->next=left;
            left=left->next;
        }
        //如果左比右大则把右的节点连接到tem后
        else {
             tem->next=right;
            right=right->next;
        }
        tem=tem->next;
        }
        //检查是否有遗落的节点
        if(left!=nullptr){
            tem->next=left;
        }
        if(right!=nullptr){
            tem->next=right;
        }
    return head->next;
    }
    
};