#include <iostream>#include <stdio.h>#include <vector>#include <string>using namespace std;/*問題:Given a singly linked list L: L0→L1→…→Ln-1→Ln,reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…You must do this in-place without altering the nodes' values.For example,Given {1,2,3,4}, reorder it to {1,4,2,3}.分析:此題就是要將最后面的結點插在第一個結點后面，倒數第二個結點插在第二個結點后面且不允許修改結點的值。如果不允許修改結點的值，那么肯定要找到末尾結點，末尾結點的前面結點這些。也就是要找到一個結點前面結點情況用一個數組A存儲所有結點不就行了，設長度為n然后A[0]指向A[n-1],A[n-1]指向A[1],A[1]指向A[n-2]只需要遍歷到len/2的結點，比如1 2 3 4 5,那么變成1 5 2 4 3輸入:1(數組元素個數)121 24 1 2 3 451 2 3 4 5輸出11 21 4 2 31 5 2 4 3*/struct ListNode {     int val;     ListNode *next;     ListNode(int x) : val(x), next(NULL) {}};class Solution {public:    void reorderList(ListNode* head) {        if(!head)		{			return;		}		vector<ListNode*> nodes;		ListNode* node = head;		while(node)		{			nodes.push_back(node);			node = node->next;		}		if(nodes.empty())		{			return ;		}		int size = nodes.size();		//設置結點指向		ListNode* nextNode = NULL;		for(int i = 0 ; i < size / 2 ; i++)		{			if(i + 1 < size)			{				nextNode = nodes.at(i+1);			}			else			{				nextNode = NULL;			}			nodes.at(i)->next = nodes.at(size - i - 1);			//當前結點不是和下一個結點相同，才指向			if(nodes.at(size - i - 1) != nextNode)			{				nodes.at(size - i - 1)->next = nextNode;			}			else			{				nodes.at(size - i - 1)->next = NULL;			}		}		//這里最后一個結點要設置為空		//size/2是最后結點，這個元素是沒有交換的		nodes.at(size/2)->next = NULL;    }};void PRint(ListNode* head){	if(!head)	{		cout << "no result" << endl;	}	ListNode* tempHead = head;	while(head)	{		cout << head->val << " ";		head = head->next;	}	cout << endl;	head = tempHead;}ListNode* buildList(vector<int>& nums){	if(nums.empty())	{		return NULL;	}	int size = nums.size();	ListNode* head ;	ListNode *tail;	ListNode* node;	for(int i = 0 ; i < size ; i++)	{		if(i)		{			node = new ListNode(nums.at(i));			tail->next = node;			tail = node;		}		else		{			head = new ListNode(nums.at(i));			tail = head;		}	}	return head;}void deleteList(ListNode* head){	ListNode* node;	while(head)	{		node = head->next;		delete head;		head = node;	}}void process(){	 vector<int> nums;	 int value;	 int num;	 Solution solution;	 vector<int> result;	 while(cin >> num )	 {		 nums.clear();		 for(int i = 0 ; i < num ; i++)		 {			 cin >> value;			 nums.push_back(value);		 }		 ListNode* head = buildList(nums);		 solution.reorderList(head);		 print(head);		 deleteList(head);//刪除節點了	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}