题解 | #排序奇升偶降链表#
排序奇升偶降链表
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;
}
};
