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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
	ListNode * HandleIt(queue<ListNode*>& ltr, stack<ListNode*>& rtl)
	{
		ListNode* p;
		if (ltr.front()->val > rtl.top()->val)
		{
			p = rtl.top();
			rtl.pop();
		}
		else
		{
			p = ltr.front();
			ltr.pop();
		}
		return p;
	}

	ListNode* sortLinkedList(ListNode* head)
	{
		if (!head->next) return head;
		//获得两条递增的线性表
		queue<ListNode*> ltr;//从左向右递增
		stack<ListNode*> rtl;//从右向左递增
		bool isOdd = true;//是否奇数
		while (head)
		{
			if (isOdd)
			{
				ltr.emplace(head);
			}
			else
			{
				rtl.emplace(head);
			}
			isOdd = !isOdd;
			head = head->next;
		}

		//找出新的链头
		ListNode* newHead = HandleIt(ltr, rtl);
		ListNode* p = newHead;

		//对两个线性表进行整合排序
		while (!ltr.empty() || !rtl.empty())
		{
			if (ltr.empty())
			{
				p->next = rtl.top();
				rtl.pop();
			}
			else if (rtl.empty())
			{
				p->next = ltr.front();
				ltr.pop();
			}
			else
			{
				p->next = HandleIt(ltr, rtl);
			}
			p = p->next;
		}
		p->next = nullptr;
		return newHead;
	}
};