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

小灰灰 2022-07-12 04:28 189阅读 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

不得使用数组！  
Author

#include<stdio.h>
    #include<stdlib.h>
    struct node
    {
        int data;
        struct node *next;
    };
    int main()
    {
        int n, count1 = 0, count2 = 0, i;
        struct node *p, *head, *tail, *head1, *head2, *tail1, *tail2;
        head = (struct node *) malloc (sizeof(struct node));
        head -> next = NULL;
        tail = head;
        head1 = (struct node *) malloc (sizeof(struct node));
        head1 -> next = NULL;
        tail1 = head1;
        head2 = (struct node *) malloc (sizeof(struct node));
        head2 -> next = NULL;
        tail2 = head2;
        scanf("%d", &n);
        for(i = 0; i < n; i++)
        {
            p = (struct node *) malloc (sizeof(struct node));
            scanf("%d", &p -> data);
            p -> next = NULL;
            tail -> next = p;
            tail = p;
        }
        p = head -> next;
        while(p != NULL)
        {
            if(p -> data % 2 == 0)
            {
                count1++;
                tail1 -> next = p;
                tail1 = p;
            }
            else
            {
                count2++;
                tail2 -> next = p;
                tail2 = p;
            }
            p = p -> next;
        }
        tail1 -> next = NULL; //确保tail1后没有元素
        tail2 -> next = NULL; 
        printf("%d %d\n", count1, count2);
        p = head1 -> next;
        while(p != NULL)
        {
            if(p -> next == NULL)
                printf("%d\n", p -> data);
            else
                printf("%d ", p -> data);
            p = p -> next;
        }
        p = head2 -> next;
        while(p != NULL)
        {
            if(p -> next == NULL)
                printf("%d\n", p -> data);
            else
                printf("%d ", p -> data);
            p = p -> next;
        }
        return 0;
    }