题解 | 单链表的排序

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {   
    //采用归并排序，拆分到最小，再合并
    //如果采用快速排序，节点的移动（删除再添加）很麻烦，且
    //总是需要被移动节点的前面一个节点，逻辑复杂
public:
    ListNode* sortInList(ListNode* head) {
        if(!head || !head->next) return head;   //当只有一个时，返回开始合并

        ListNode *slow = head, *fast = head;  
        while(fast->next && fast->next->next){
            slow = slow->next;
            fast = fast->next->next;
        }

        ListNode *mid = slow->next;
        slow->next = nullptr;   //断开连接，合并的时候需要检查空；
        ListNode *left = sortInList(head);
        ListNode *right = sortInList(mid);

        return merge(left, right);  //合并
    }

    ListNode* merge(ListNode *l1, ListNode *l2){
        ListNode dummy(0);
        ListNode *tail = &dummy;

        while(l1 && l2){    
            if(l1->val < l2->val){  //连接，移动指针即可
                tail->next = l1;
                l1 = l1->next;
                tail = tail->next;
            }else{
                tail->next = l2;
                l2 = l2->next;
                tail = tail->next;
            }
        }

        tail->next = l1? l1:l2;
        return dummy.next;
    }
};