将一个线性表拆解为两个线性表

问题描述：

设C={a1, b1, a2, b2, …, an, bn}为线性表，釆用带头结点的hc单链表存放，设计一个就地算法，将其拆分为两个线性表，使得A={a1, a2,…, an}, B={bn, …, b2, b1}。

问题解答：

算法思想：釆用上题的思路，不设序号变量。二者的差别仅在于对B，表的建立不采用尾插法，而是釆用头插法。

LinkList DisCreat_2(LinkList &A){
    LinkList B= (LinkList)malloc(sizeof(LNode)) ;  //创建B 表表头
    B->next=NULL;  //B 表的初始化
    LNode *p=A->next, *q;  //p 为工作指针
    LNode *ra=A;  //ra始终指向A的尾结点
    while(p!=NULL){
        ra->next=p;  ra=p;  //将*p 链到 A 的表尾
        p=p->next;
        q=p->next;  //头插后，将断链，因此用q记忆*p的后继
        p->next=B->next;  //将插入到 B 的前端
        B->next=p;
        p=q
    }
    ra->next=NULL;  //A尾结点的next域置空
    return B;
}

该算法特别需要注意的是，釆用头插法插入结点后，*p的指针域已改变，如果不设变量保存其后继结点会引起断链，从而导致算法出错。