leecode 解题总结：143. Reorder List

#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;}