SDUTACM 数据结构实验之链表五：单链表的拆分

灰太狼 2022-07-16 02:49 62阅读 0赞

#### Problem Description ####

输入N个整数顺序建立一个单链表，将该单链表拆分成两个子链表，第一个子链表存放了所有的偶数，第二个子链表存放了所有的奇数。两个子链表中数据的相对次序与原链表一致。

#### Input ####

第一行输入整数N;；  
第二行依次输入N个整数。

#### Output ####

第一行分别输出偶数链表与奇数链表的元素个数；  
第二行依次输出偶数子链表的所有数据；  
第三行依次输出奇数子链表的所有数据。

#### Example Input ####

10
    1 3 22 8 15 999 9 44 6 1001

#### Example Output ####

4 6
    22 8 44 6 
    1 3 15 999 9 1001

#### Hint ####

#include<stdio.h>
    #include<stdlib.h>
    struct hh
    {
        int data;
        struct hh *next;
    };
    int main()
    {
        struct hh *head,*p,*t,*head1,*p1,*t1,*head2,*p2,*t2;
        int n,i,x,y;
        head=(struct hh *)malloc(sizeof(struct hh));
        head1=(struct hh *)malloc(sizeof(struct hh));
        head2=(struct hh *)malloc(sizeof(struct hh));
        head1->next=NULL;
        t1=head1;
        head2->next=NULL;
        t2=head2;
        head->next=NULL;
        t=head;
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
                p=(struct hh *)malloc(sizeof(struct hh));
                scanf("%d",&p->data);
                p->next=t->next;
                t->next=p;
                t=p;
        }
        x=0;
        y=0;
        p=head->next;
        while(p!=NULL)
        {
            if(p->data%2!=0)
            {
                p1=(struct hh *)malloc(sizeof(struct hh));
                p1->data=p->data;
                p1->next=t1->next;
                t1->next=p1;
                t1=p1;
                x++;
            }
            else if(p->data%2==0)
            {
                p2=(struct hh *)malloc(sizeof(struct hh));
                p2->data=p->data;
                p2->next=t2->next;
                t2->next=p2;
                t2=p2;
                y++;
            }
            p=p->next;
        }
        printf("%d %d\n",y,x);
        p2=head2->next;
        for(i=0;i<y-1;i++)
        {
            printf("%d ",p2->data);
            p2=p2->next;
        }
        printf("%d\n",p2->data);
        p1=head1->next;
        for(i=0;i<x-1;i++)
        {
            printf("%d ",p1->data);
            p1=p1->next;
        }
        printf("%d\n",p1->data);
        return 0;
    }