题解 | 单链表的排序

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
   ListNode* merge(ListNode* pHead1, ListNode* pHead2) {
        //一个已经为空了，直接返回另一个
        if(pHead1 == NULL)
            return pHead2;
        if(pHead2 == NULL)
            return pHead1;
        //加一个表头
        ListNode* head = new ListNode(0);
        ListNode* cur = head;
        //两个链表都要不为空
        while(pHead1 && pHead2){
            //取较小值的节点
            if(pHead1->val <= pHead2->val){
                cur->next = pHead1;
                //只移动取值的指针
                pHead1 = pHead1->next;
            }else{
                cur->next = pHead2;
                //只移动取值的指针
                pHead2 = pHead2->next;
            }
            //指针后移
            cur = cur->next;
        }
        //哪个链表还有剩，直接连在后面
        if(pHead1)
            cur->next = pHead1;
        else
            cur->next = pHead2;
        //返回值去掉表头
        return head->next;
    }
     
    ListNode* sortInList(ListNode* head) {
        //链表为空或者只有一个元素，直接就是有序的
        if(head == NULL || head->next == NULL)
            return head;
        ListNode* left = head;
        ListNode* mid = head->next;
        ListNode* right = head->next->next;
        //右边的指针到达末尾时，中间的指针指向该段链表的中间
        while(right != NULL && right->next != NULL){
            left = left->next;
            mid = mid->next;
            right = right->next->next;
        }
        //左边指针指向左段的左右一个节点，从这里断开
        left->next = NULL;
        //分成两段排序，合并排好序的两段
        return merge(sortInList(head), sortInList(mid));
    }
};



/*ListNode* sortInList(ListNode* head) {//超时了
    if(!head || !head->next) return head;
    bool swapped;
    ListNode* pre = head;
    ListNode* cur = nullptr;
    while(pre) {
        swapped = false;
        cur = pre->next;
        while(cur) {
            if(pre->val > cur->val) {
                int temp = pre->val;
                pre->val = cur->val;
                cur->val = temp;
                swapped = true;
            }
            cur = cur->next;
        }
        if(!swapped) break; // 优化：若未发生交换，提前结束
        pre = pre->next;
    }
    return head;
}*/