//***********************************
//功能：对于单链表A，把位序为奇数的元素放在后半部分，保持原相对次序；位序为偶数的元素放在前半部分，并且反序，保持原相对次序；利用原结点内存空间
//日期：2017年10月10日
//作者：Ryan2019
//***********************************
#include <iostream>
using namespace std;
typedef int LElemType;
typedef struct LNode
{
    LElemType data;
	LNode *next;
}* LList;
void ListCreate(LList &L,int n,LElemType a[]);//创建链表
void Listshow(LList &L);//显示链表
bool Divide(LList &L);//反偶数位序的单链表

int main()
{
	LList L; int m=6;
	LElemType a[6]={1,2,3,4,5,6};
	for(int i=0;i<=m;i++)
	{
	ListCreate(L,i,a);	
	cout<<"原链表为：";Listshow(L);
	Divide(L);
	cout<<"改变元素次序后的单链表为：";	Listshow(L);	
	}
	return 0;
}

void ListCreate(LList &L,int n,LElemType a[])
{
	LList p;	int i;
	L=new LNode; L->next=NULL;
	for(i=n-1;i>=0;i--)
	{
		p=new LNode;
		p->data=a[i];
		p->next=L->next;
		L->next=p;
	}
}
void Listshow(LList &L)
{
	LList p;
	for(p=L->next;p;p=p->next)
	{
		cout<<p->data<<" ";
	}
	cout<<endl;
}

bool Divide(LList &L)
 {  
	LList p,q,r;
	p = L->next;
	if(!p) return true;
	L->next=NULL;
	r=L;
	while (p)
	{
		r->next=p;
		r=p;
		p=p->next;
		r->next=NULL;
		if(!p) break;				
		q=p;
		p=p->next;
		q->next=L->next;
		L->next=q;		
	}
	return true;
}