41.（13分）设线性表L=（a1，a2，a3…，an-2，an-1，an）采用带头结点的单链表保存，链表中的结点定义如下： typedef struct node { int data; struct node*next; }NODE; 请设计一个空间复杂度为O（1）且时间上尽可能高效的算法，重新排列L中的各结点，得到线性表L'=（a1，an，a2，an-1，a3，an-2，...）。要求： （1）给出算法的基本设计思想。 （2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。 （3）说明你所设计的算法的时间复杂度。
【参考答案及解析】
（1）算法的基本设计思想∶先观察L（a1，a2，a3，……，an-2，an-1，an）和L'（a1，an，a2，an-1，a3，an-2，……），发现L'是由L摘取第一个元素，再摘取倒数第一个元素……依次合并而成的。为了方便链表后半段取元素，需要先将L后半段原地逆置 【题目要求空间复杂度为O（1），不能借助栈】，否则每取最后一个结点都需要遍历一次链表。①先找出链表L的中间结点，为此设置两个指针p和q，指针p 每次走一步，指针g每次走两步，当指针q到达链尾时，指针p正好在链表的中间结点;②然后将 L 的后半段结点原地逆置。③从单链表前后两段中依次各取一个结点，按要求重排。 （2）算法实现∶ void change_list(NODE *h){ NODE *p,*q,*r,*s; p=q=h; while（q->next!=NULL）{ // 寻找中间结点 D=p->next;//p 走一步 q=q->next; if（q->next!=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; } } （3）第1步找中间结点的时间复杂度为O（n），第 2步逆置的时间复杂度为 O（n），第3步合并链表的时间复杂度为 O（n），所以该算法的时间复杂度为 O（n）。
正在整理中,欢迎在文下评论区提供答案解析,谢谢！
（1）算法的基本设计思想∶先观察L（a1，a2，a3，……，an-2，an-1，an）和L'（a1，an，a2，an-1，a3，an-2，……），发现L'是由L摘取第一个元素，再摘取倒数第一个元素……依次合并而成的。为了方便链表后半段取元素，需要先将L后半段原地逆置 【题目要求空间复杂度为O（1），不能借助栈】，否则每取最后一个结点都需要遍历一次链表。①先找出链表L的中间结点，为此设置两个指针p和q，指针p 每次走一步，指针g每次走两步，当指针q到达链尾时，指针p正好在链表的中间结点;②然后将 L 的后半段结点原地逆置。③从单链表前后两段中依次各取一个结点，按要求重排。 （2）算法实现∶ void change_list(NODE *h){ NODE *p,*q,*r,*s; p=q=h; while（q->next!=NULL）{ // 寻找中间结点 D=p->next;//p 走一步 q=q->next; if（q->next!=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; } } （3）第1步找中间结点的时间复杂度为O（n），第 2步逆置的时间复杂度为 O（n），第3步合并链表的时间复杂度为 O（n），所以该算法的时间复杂度为 O（n）。
正在整理中,欢迎在文下评论区提供答案解析,谢谢！