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

排序奇升偶降链表

http://www.nowcoder.com/practice/3a188e9c06ce4844b031713b82784a2a

对于这题，可以先遍历一次，用队列保存递增的奇数位指针，用栈保存递减的偶数位指针。

这两个线性表输出的将都是递增的序列。那么逐个比较两个表的元素，然后小的先加入新链表，即可得出答案。

例如：

1->10->2->9->8->3->9->1

用队列保存1->2->8->9，再输出将是1->2->8->9

用栈保存10->9->3->1，再输出将是1->3->9->10

那么得出答案1->1->2->3->8->9->9->10

/**
 * 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;
	}
};