难度:Medium
给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1:
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
示例 2:
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
Method: Stack's FILO
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
void reorderList(ListNode* head) {
if(!head || !head->next || !head->next->next) return;
ListNode* mid= head;
ListNode* last=head;
while( last->next && last->next->next)
{
mid=mid->next;
last=last->next->next;
}
stack<ListNode*> lastMid;
last=mid->next;
mid->next=nullptr;
while(last)
{
ListNode* tmp=last;
last=last->next;
tmp->next=nullptr;
lastMid.push(tmp);
}
ListNode* cur=head;
while(!lastMid.empty())
{
ListNode* tmp= lastMid.top();
tmp->next= cur->next;
cur->next=tmp;
lastMid.pop();
cur=tmp->next;
}
}
};
执行用时 :68 ms, 在所有 C++ 提交中击败了31.46%的用户
内存消耗 :18.1 MB, 在所有 C++ 提交中击败了9.17%的用户