题解 | 排序奇升偶降链表

class Solution {
public:
    ListNode* sortLinkedList(ListNode* head) {
        ListNode dummy(0);
        ListNode *noddList = &dummy;

        ListNode *curr = head;
        
        //链表分解，奇位一起，偶位一起，拼接+断开
        while(curr && curr->next){
            noddList->next = curr->next;
            curr->next = curr->next->next;
            noddList->next->next = nullptr;//断开链接

            noddList = noddList->next; //移动到下一个拼接点

            curr = curr->next;
        }

        //链表反转
        noddList = &dummy;
        curr = dummy.next;
        ListNode* prev = nullptr;
        while(curr){
            ListNode* temp = curr->next;

            curr->next = prev;

            prev = curr;
            curr = temp;
        }
        dummy.next = prev;

        //链表拼接
        ListNode ansdummy(0);
        ListNode *ans = &ansdummy;
        ListNode* odd = head;
        ListNode* oven = dummy.next;
        while(odd && oven){
            if(odd->val < oven->val){
                ans->next = odd;
                odd = odd->next;
            }else{
                ans->next = oven;
                oven = oven->next;
            }
            ans = ans->next;  //记得指针要移动到要拼接的节点
        }

        if(odd){
            ans->next = odd;
        }else{
            ans->next = oven;
        }

        return ansdummy.next;
    }
};