143.Reorder List

143.Reorder List

难度: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%的用户