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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* mergeHelp(ListNode* head1,ListNode* head2){       //合并两个升序链表
        if(head1 == nullptr)
            return head2;
        if(head2 == nullptr)
            return head1;
        ListNode* newHead = head1->val >= head2->val ? head2 : head1;      //头节点值小的作为新的头节点
        ListNode* otherHead = head1->val >= head2->val ? head1 : head2;        //选定另一个链表
        ListNode* cur1 = newHead->next, * cur2 = otherHead;
        ListNode* cur1_pre = newHead;
        while(cur1 && cur2){
            if(cur1->val >= cur2->val){  //把cur2的当前节点插入到cur1的前一个位置
                cur1_pre->next = cur2; 
                cur2 = cur2->next;   
                cur1_pre->next->next = cur1;   //把新加的节点后继连向cur1节点
                cur1_pre = cur1_pre->next;  //cur1_pre确保始终在cur1的前一个节点
            }else{
                cur1_pre = cur1;   
                cur1 = cur1->next;
            }
        }
      //这里如果cur1没到空，说明cur2的最大值小于cur1的最大值，我们又选定cur1作为新链表的头节点，所以可以直接返回
      //如果cur2没到空，说明cur2的最大值大于cur1的最大值，所以要把cur1的最后一个节点连向当先cur2的位置
      */
        if(cur2){
            cur1_pre->next = cur2;
        }
        return newHead;
    }
    
    ListNode* verseList(ListNode* head){   //将降序链表反转成升序
        if(head == nullptr || head->next == nullptr)
            return head;
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while(cur){
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
    
    ListNode* sortLinkedList(ListNode* head) {
        // write code here
        if(head == nullptr || head->next == nullptr)
            return head;
        ListNode* head1 = head;
        ListNode* head2 = head->next;
        ListNode* cur1 = head1,* cur2 = head2;
        while(cur2 && cur2->next){   //拆分链表，一条为奇数节点，一条为偶数节点
            cur1->next = cur2->next;
            cur1 = cur1->next;
            cur2->next = cur1->next;
            cur2 = cur2->next;
        }
        cur1->next = nullptr;		//注意两条链表的尾部要指向nullptr
        head2 = verseList(head2);	//反转降序链表成升序
        return merge(head1,head2);		//合并两个升序链表
    }
};