将一个单链表分解为两个单链表A和B

问题描述：

将一个带头结点的单链表A分解为两个带头结点的单链表A和B，使得A表中含有原表中序号为奇数的元素，而B表中含有原表中序号为偶数的元素，且保持其相对顺序不变。

问题解答：

算法思想：设置一个访问序号变量（初值为0），每访问一个结点序号自动加1，然后根据序号的奇偶性将结点插入到A表或B表中。重复以上操作直到表尾。

LinkList DisCreat_1(LinkList &A){
    //将表A中结点按序号的奇偶性分解到表A或表B中
    i=0;  //i记录表A中结点的序号
    B= (LinkList) malloc (sizeof (LNode) );  //创建 B 表表头
    B->next=NULL;  //B 表的初始化
    LNode *ra = A, *rb=B;  //ra和rb将分别指向将创建的A表和B表的尾结点
    p=A->next;  //p为链表工作指针，指向待分解的结点
    A->next=NULL;  //置空新的 A 表
    while (p!=NULL) {
        i++;  //序号加 1
        if (i%2==0) {  //处理序号为偶数的链表结点
            rb->next=p;  // 若B表尾描入新结点
            rb=p;  //rb指向新的尾结点
        }else{    //处理原序号为奇数的结点
            ra->next=p;  //在A表尾插入新结点
            ra=p;
        }
        p=p->next;  //将p恢复为指向新的待处理结点
    }  //while 结束
    ra->next=NULL;
    rb->next=NULL;
    return B;
}

为了保持原来结点中的顺序，本题用尾插法建立单链表。此外，本算法完全可以不用设置序号变量。while循环中的代码改为将结点插入到表A中和将下一结点插入到表B中，这样while中第一处理的结点就是奇数号结点，第二处理的结点就是偶数号结点。