SDUT-2120_数据结构实验之链表五：单链表的拆分

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

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

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

Input

第一行输入整数N;；

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

Output

第一行分别输出偶数链表与奇数链表的元素个数；

第二行依次输出偶数子链表的所有数据；

第三行依次输出奇数子链表的所有数据。

Sample Input

10

1 3 22 8 15 999 9 44 6 1001

Sample Output

4 6

22 8 44 6

1 3 15 999 9 1001

Hint

不得使用数组！

依旧考验链表的插入操作，将不同的节点插入不同的链表，注意不要忘了在链表结尾加结束标志。

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

typedef struct node

{

    int data;

    struct node *next;

}link;

link *newlink()

{

    link *t;

    t = (link*)malloc(sizeof(link));

    t->next = NULL;

    return t;

}

link *create(int n)

{

    link *head,*p,*q;

    int i;

    head = newlink();

    p = head;

    for(i=0;i<n;i++)

    {

        q = newlink();

        scanf("%d",&q->data);

        q->next = NULL;

        p->next = q;

        p = q;

    }

    return head;

}

void show(link *head)

{

    link *p;

    p = head->next;

    while(p)

    {

        if(p->next==NULL)

            printf("%d\n",p->data);

        else

            printf("%d ",p->data);

        p = p->next;

    }

}

void Chaifen(link *head)

{

    link *head1,*r,*p,*q;

    int m,n;

    m = n = 0;

    r = head->next;

    head1 = newlink();

    head->next = NULL;

    p = head1;

    q = head;

    while(r)

    {

        if(r->data%2)

        {

            p->next = r;

            p = p->next;

            r = r->next;

            m++;

        }

        else

        {

            q->next = r;

            q = q->next;

            r = r->next;

            n++;

        }

    }

    p->next = NULL;//结束标志

    q->next = NULL;//结束标志

    printf("%d %d\n",n,m);

    show(head);

    show(head1);

}

int main()

{

    link *head;

    int n;

    scanf("%d",&n);

    head = create(n);

    Chaifen(head);

    return 0;

}

巴特西