/*设线性表L=(a1,a2,a3,...,an-2,an-1,an)采用带头结点的单链表保存,链表的结构为data、next。请设计一个空间复杂度为O(1)且时间上尽可能高效的算法,重新排列L中的各结点,得到线性表L'=(a1,an,a2,an-1,a3,an-2)。*/#include<stdio.h>#include<stdlib.h>typedef int ElemType;typedef struct LNode{ElemType data;struct LNode *next;}LNode,*LinkList;LinkList tailInsertList(LinkList &L){ElemType x;L = (LinkList)malloc(sizeof(LNode));LNode *r=L;scanf("%d",&x);while(x!=9999){LNode *s = (LNode*)malloc(sizeof(LNode));s->data = x;r->next = s;r = s;scanf("%d",&x);}r->next = NULL;return L;}LinkList operLink(LinkList &L){LNode *p=L,*q=L;LNode *r,*s;while(q->next){p = p->next;q = q->next;if(q->next)q = q->next;}//此时p为中间结点q = p->next; //q为后部首结点//将q为首的后部结点进行逆置p->next = NULL;while(q){r = q->next;q->next = p->next;p->next = q;q = r;}s = L->next;q = p->next;p->next = NULL;while(q){r = q->next;q->next = s->next;s->next = q;s = q->next;q = r;}return L;} bool printList(LinkList L){LNode *p = L->next;while(p){printf("%d ",p->data);p = p->next;}printf("\n");return true;}void main(){LinkList L;tailInsertList(L);operLink(L);printList(L);}