题解 | #排序奇升偶降链表#

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    ListNode* newhead = new ListNode(-1);//最后返回的链表
    ListNode* j = new ListNode(-1);//奇位数头
    ListNode* ta1 = new ListNode(-1);//奇位数尾部
    ListNode* ou = new ListNode(-1);//偶位数头
    ListNode* ta2 = new ListNode(-1);//偶位数尾部
    ListNode* sortLinkedList(ListNode* head) {
        // write code here

        ta1 = j;
        ta2 = ou;
        ListNode* pre = head;
        ListNode* cur = head->next;
        while (pre || cur) {
            if (pre) {
                pre = ji(pre);//读取奇位数
            }
            if (cur) {
                cur = ouu(cur);//读取偶位数
            }

        }
        ou->next = rev(ou->next);//因为读取偶位数是顺序读取，需要对其元素进行反转
        ListNode* tail = newhead;
        while (ou->next && j->next) {//遍历奇偶位数链表，选取小的添加如最后需要返回的链表
            if (ou->next->val > j->next->val) {
                ListNode* temp = j->next->next;
                tail->next = j->next;
                tail = tail->next;
                tail->next = nullptr;
                j->next = temp;
            } else {
                ListNode* temp = ou->next->next;
                tail->next = ou->next;
                tail = tail->next;
                tail->next = nullptr;
                ou->next = temp;
            }
        }//对可能存留的链表数据进行连接
        if (ou->next) {
            tail->next = ou->next;
        }
        if (j->next) {
            tail->next = j->next;
        }
        return newhead->next;
    }
    ListNode* rev(ListNode* head) {//反转函数
        ListNode* newhead = new ListNode(-1);
        while (head) {
            ListNode* temp = head->next;
            head->next = newhead->next;
            newhead->next = head;
            head = temp;
        }
        return newhead->next;
    }
    ListNode* ji(ListNode* pre) {//奇位数链表维护
        ListNode* temp;
        if (pre->next == nullptr) {
            temp = nullptr;
        } else {
            temp = pre->next->next;

        }

        ta1->next = pre;
        pre->next = nullptr;
        ta1 = ta1->next;
        return temp;
    }
    ListNode* ouu(ListNode* cur) {//偶位数链表维护
        ListNode* temp;
        if (cur->next == nullptr) {
            temp = nullptr;
        } else {
            temp = cur->next->next;
        }

        ta2->next = cur;
        cur->next = nullptr;
        ta2 = ta2->next;
        return temp;
    }
};