《C语言及程序设计》实践参考——拆分链表

返回：贺老师课程教学链接

【项目2-拆分链表】
编写一个函数将一个头指针为a的单链表A分解成两个单链表A和B，其头指针分别为a和b，使得A链表中含有原链表A中序号为奇数的元素，而B链表中含有原链表A中序号为偶数的元素，且保持原来的相对顺序。例，建立长度为7，元素为1 2 3 4 5 6 7的链表后，经拆分，得到两个数组A和B，其元素分别是1 3 5 7 和2 4 6

[参考解答]

#include <stdio.h>
#include <stdlib.h>
typedef struct s
{
    int date;
    struct s *link;
} S;
S *creat(int n)
{
    S *p,*q,*head;
    head=p=q=malloc(sizeof(S));
    scanf("%d",&p->date);
    while(--n)
    {
        p=malloc(sizeof(S));
        scanf("%d",&p->date);
        q->link=p;
        q=p;
    }
    q->link=NULL;
    return head;
}
void play(S *h,int n)
{
    S *p,*q,*h1=h,*h2=h->link;
    int i;
    for(p=h1,q=h2,i=0; p!=NULL && q!=NULL && i<(n+1)/2-1; i++)
    {
        p->link=p->link->link;
        q->link=q->link->link;
        p=p->link;
        q=q->link;
    }
    if(!(n%2))
    {
        q=NULL;
        p=NULL;
    }
    else
        p->link=NULL;
    for(p=h1,i=1; i<=(n+1)/2; p=p->link,i++)
        printf("%d ",p->date);
    printf("\n");
    for(p=h2,i=1; p!=NULL; p=p->link,i++)
        printf("%d ",p->date);
    printf("\n");
}
int main()
{
    int n;
    scanf("%d",&n);
    play(creat(n),n);
    return 0;
}