[数据结构与算法]重新排列（21.6.6）

题目描述：

设线性表L=（a1,a2,a3…an），采用带头结点的单链表来保存，设计一个原地算法使L中的元素重新排列，使之变成L=（a1,an,a2,…）,要求时间上尽可能高效。

算法思路：

观察可知新的链表是在原来链表基础上摘取第一个元素，再摘取最后一个元素…依次拼接而成。为了方便取后面的元素，需要将原来线性表的后半部分原地逆置。此时先找到链表的中间结点，可以设置两个指针，一个p指针，一个q指针，前者每次走一个，后者每次走两步，这样当q指针走到线性表最后一个元素时，此时p指针指向的就是链表的中间元素。然后将L的后半段结点原地逆置，从单链表中前后两段依次取下第一个结点重新拼接成新的链表即可。

代码实现：

void change_list(Node *h){
	Node *P,*q,*r,*s;
	p=q=h;
	while(q->next != NULL){  //寻找中间结点 
		p=p->next;
		q=q->next;
		if(q->next!=NULL) q=q->next;
	}
	q=p->next;  //此时p指向中间结点，这样使q指向后半段链表的第一个结点
	p->next=NULL;
	while(q!=NULL){  //后半段链表进行逆置 
		r=q->next;
		q->next=p->next;
		p->next=q;
		q=r;
	}
	s=h->next; //s指向前半段的第一个数据结点，即插入点 
	q=p->next; //q为指向后半段的第一个数据结点 
	p->next=NULL;
	while(q!=NULL){  //将链表后半段的结点插入到指定位置 
		r=q->next;  //r指向后半段的下一个结点 
		q->next=s->next;   //将q所指的结点插入到s所指的结点之后 
		s->next=q;
		s=q->next;  //s指向前半段的下一个插入点 
		q=r;
	}
}