38-11

设C={a1,b1,a2,b2,.....,an,bn}；使用带头结点的单链表，将C分割成A={a1,a2,a3,....,an}；,B={bn,bn-1,....,b2,b1};

注意B是逆置，应采用头插法

对于abababab这种结点，可以使用count记录奇偶，也可以一个while循环中分别对A，B进行插入

#include <stdio.h>
#include <stdlib.h>

typedef struct node{
    int data;
    struct node *next;
}LNode,*LinkList;

void TailCreate(LinkList &L)
{
    L=(LinkList)malloc(sizeof(LNode));
    L->next=NULL;
    LNode *p,*r=L;
    int x;
    scanf("%d",&x);
    while(x!=999)
    {
        p=(LNode*)malloc(sizeof(LNode));
        p->data=x;
        p->next=NULL;
        r->next=p;
        r=p;
        scanf("%d",&x);
    }
}

void displayList(LinkList L)
{
    LNode *p=L->next;
    while(p!=NULL)
    {
        printf("%d  ",p->data);
        p=p->next;
    }
}

void Split(LinkList &L)
{
    LNode *A=(LNode*)malloc(sizeof(LNode));
    LNode *B=(LNode*)malloc(sizeof(LNode));
    A->next=NULL;
    B->next=NULL;
    LNode *pa=A,*pb=B,*p=L->next,*r;
    while(p)
    {
        pa->next=p;
        pa=p;
        p=p->next;
        if(p)
        {
            r=p->next;
            p->next=pb->next;
            pb->next=p;
            p=r;    
        }    
    }    
    pa->next=NULL;
    free(L);
    displayList(A);
    printf("\n");
    displayList(B);
} 

int main()
{
    LinkList L;
    TailCreate(L);
    displayList(L);
    printf("\n");
    Split(L);
    return 0;
}