[数据结构与算法]长度为n的单链表L=(L1...Ln)，转化成LT(L1LnL2Ln-1L3Ln-2...)

C语言实现如下

# include<stdio.h>
typedef char Elem;
typedef struct Linknode
{
    Elem data;
    struct Linknode *next;
} Linknode,*Linklist;

//创建链表，尾插
void createLink(Linklist *L)
{
    (*L)=(Linklist )malloc(sizeof(Linknode));
    Linknode *tail=(Linknode *)malloc(sizeof(Linknode));
    Elem data;
    scanf("%c",&data);
    tail->data=data;
    tail->next=NULL;
    (*L)->next=tail;
    if(data=='#')
    {
        return;
    }
    while(1)
    {
        scanf("%c",&data);
        if(data=='#')
        {
            return;
        }
        Linknode *pnode = (Linknode *)malloc(sizeof(Linknode));
        pnode->data=data;
        pnode->next=NULL;
        tail->next=pnode;
        tail=tail->next;
    }

}
void print(Linklist L)
{
    if(L==NULL)
        return;
    Linknode *pnode=L->next;
    while(pnode)
    {
        printf("%c\n",pnode->data);
        pnode=pnode->next;
    }
}
void reverse(Linklist L)
{
    if(L==NULL)
    {
        return ;
    }
    Linknode *pnode=L->next;
    L->next=NULL;

    while(pnode)
    {
        Linknode *temp=pnode;
        pnode=pnode->next;
        temp->next=L->next;
        L->next=temp;
    }

}

//截取子链
Linklist getSublink(Linklist L,Linklist *subL)
{
    if(L==NULL)
    {
        return ;
    }
    Linknode *pnode1=L->next;
    Linknode *pnode2=L->next;
    *subL=(Linklist)malloc(sizeof(Linknode));
    (*subL)->next=NULL;
    if(pnode2!=NULL)
        pnode2=pnode2->next;
    while(pnode1&&pnode2)
    {
        pnode1=pnode1->next;
        pnode2=pnode2->next;
        if(pnode2!=NULL)
        {
            pnode2=pnode2->next;
        }
        //printf("%c %c\n",pnode1->data,pnode2->data);
    }
    (*subL)->next=pnode1->next;
    pnode1->next=NULL;

    //print(L);

    return (*subL);
}
//开始插入
void insertL(Linklist L,Linklist subL)
{
    if(L==NULL || subL==NULL)
        return ;
    Linknode *pnode1=L->next;
    Linknode *pnode2=subL->next;
    while(pnode1&&pnode2)
    {

        Linknode *temp2=pnode2;
        pnode2=pnode2->next;
        //头插法插入
        temp2->next=pnode1->next;
        pnode1->next=temp2;

        Linknode *temp1=pnode1->next;
        pnode1=temp1->next;
    }
}
int main()
{
    Linklist L;
    Linklist subL;
    createLink(&L);
    //print(L);
    //reverse(L);
    //print(L);
    subL=getSublink(L,&subL);
    reverse(subL);
    // print(subL);
    insertL(L,subL);
    print(L);
    return 0;
}