设线性表L=（a1 ，a2，a3，···，an-2,a

第1题

设线性表L=（a₁ ，a₂，a₃，···，a_n-2,a_n-1, a_n）采用带头结点的单链表保存，链表中的 结点定义如下：

typedef struct node
{ int data; 
struct node*next; 
} NODE；

请设计一个空间复杂度为 O(1)且时间上尽可能高效的算法，重新排列 L 中的各结点，得到 线性表L' =（a1 ，a_n, a₂，a_n-1,a₃，a_n-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 每次走一步，指针 q 每次走两步，当指针 q 到达链尾时，指针 p 正 好在链表的中间结点；②然后将 L 的后半段结点原地逆置。③从单链表前后两段中依次各取 一个结点，按要求重排。 

（2）算法实现：

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->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)。