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

朴灿烈づ我的快乐病毒、 2022-07-15 10:12 148阅读 0赞

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

Time Limit: 1000MS  Memory Limit: 65536KB

#### 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 ####

不得使用数组！

#### Author ####

#include<stdio.h>
    #include<stdlib.h>
    struct node
    {
    int data;
    struct node *next;
    };
    struct node *creat(struct node *head,int n)
    {
    int i;
    struct node *p,*q;
    q=head;
    for(i=0;i<n;i++)
    {
    p=(struct node *)malloc(sizeof(struct node));
    scanf("%d",&p->data);
    p->next=q->next;
    q->next=p;
    q=p;
    }
    return head;
    }
    int main()
    {
    int i,j,n,m,k,t;
    struct node *head,*head1,*p,*q,*tail;
    head=(struct node *)malloc(sizeof(struct node));
    head->next=NULL;
    head1=(struct node *)malloc(sizeof(struct node));
    head1->next=NULL;
    scanf("%d",&n);
    head=creat(head,n);
    p=head;
    tail=head1;
    k=0;
    for(i=0;i<n;i++)
    {
    if(p->next->data%2==0)
    {
    k++;
    q=p->next;
    p->next=q->next;
    q->next=tail->next;
    tail->next=q;
    tail=q;
    }
    else
    p=p->next;
    }
    printf("%d %d\n",k,n-k);
    p=head1;
    p=p->next;
    i=0;
    while(p!=NULL)
    {
    if(i==0)
    printf("%d",p->data);
    else
    printf(" %d",p->data);
    p=p->next;
    i++;
    }
    printf("\n");
    p=head;
    p=p->next;
    i=0;
    while(p!=NULL)
    {
    if(i==0)
    printf("%d",p->data);
    else
    printf(" %d",p->data);
    p=p->next;
    i++;
    }
    printf("\n");
    }