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

港控/mmm° 2022-06-01 05:39 131阅读 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

#include <stdio.h>
    #include <stdlib.h>
    struct sdut
    {
        int data;
        struct sdut *next;
    };
    int main()
    {
        int n, i, count1 = 0, count2 = 0;
        scanf("%d", &n);
        struct sdut *head1, *tail, *p, *q, *head2, *tail1, *tail2;
        head1 = (struct sdut*) malloc (sizeof(struct sdut));
        head2 = (struct sdut*) malloc (sizeof(struct sdut));
        head1 -> next = NULL;
        tail = head1;
        for(i = 0; i < n; i++)
        {
            p = (struct sdut*) malloc (sizeof(struct sdut));
            scanf("%d", &p -> data);
            p -> next = NULL;
            tail -> next = p;
            tail = p;
        }
        head2 -> next = NULL;
        q = head1 -> next;
        p = q -> next;
        head1 -> next = NULL;
        tail1 = head1;
        tail2 = head2;
        while(q)
        {
            if(q -> data % 2 == 0)
            {
                count1++;
                 q -> next = tail1 -> next;
                 tail1 -> next = q;
                 tail1 = q;
            }
            else
            {
                count2++;
                q -> next = tail2 -> next;
                tail2 ->  next = q;
                tail2 = q;
            }
            q = p;
            if(p)
                p = p -> next;
        }
        printf("%d %d\n", count1, count2);
        p = head1 -> next;
        while(p)
        {
            if(p -> next)
            {
                printf("%d ", p -> data);
            }
            else
            {
                printf("%d\n", p -> data);
            }
            p = p -> next;
        }
        p = head2 -> next;
        while(p)
        {
            if(p -> next)
            {
                printf("%d ", p -> data);
            }
            else
            {
                printf("%d\n", p -> data);
            }
            p = p -> next;
        }
        return 0;
    }