问答题
设线性表L=(a1，a2，a3，…，an-2，an-1，an)采用带头结点的单链表保存，链表中结点定义如下：
typedef struct node
{ int data;
struct node * next;
} NODE;
请设计一个空间复杂度为O(l)且时间上尽可能高效的算法，重新排列L中的各结点，得到线性表L'=(a1, an, a2, an-1, an-2,…)。
要求：
【正确答案】算法的基本设计思想： 算法分3步完成。第1步，采用两个指针交替前行，找到单链表的中间结点；第2步，将单链表的后半段结点原地逆置；第3步，从单链表前后两段中依次各取一个结点，按要求重排。
【答案解析】
问答题
根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
【正确答案】算法实现： void change_list(NODE * h) { NODE *p,* q,* r,* s; p=q=h: while(q-＞next ! =NULL) //寻找中间结点 { p=p-＞next; //p走一步 q=q-＞next; if(q-＞nexL!=NULL)q=q-＞next;//q走两步 } 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; } }
【答案解析】
【正确答案】算法的时间复杂度： 参考答案的时间复杂度为O(n)。
【答案解析】