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

TimeLimit: 1000MS Memory Limit: 65536KB

SubmitStatistic

ProblemDescription

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

Input

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

Output

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

ExampleInput

10

1 3 22 8 15 999 9 44 6 1001

ExampleOutput

4 6

22 8 44 6

1 3 15 999 9 1001

Hint

不得使用数组！

Author

E
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
//#include<dqeue>
using namespace std;

struct node
{

  int data;
  struct node*next;

};
struct  node*creat(struct node*head,int n)
{
      head= (struct node*)malloc(sizeof(struct node));
      head->next =NULL;

      struct node*tail = head;
      for(int i=1;i<=n;i++)
      {
          struct node*p = (struct node*)malloc(sizeof(struct node));
          p->next =NULL;
         scanf("%d",&p->data);
         tail->next = p;
         tail = p;

      }

      return head;



}
/*struct node*guibing(struct node*head1,struct node*head2)
{

    head1= head1->next;
    head2 =head2->next;
    struct node*tail,*p,*mail;
    tail = (struct node*)malloc(sizeof(struct node));
    mail =  tail;
    while(head1&&head2)
    {

        if(head1->data<head2->data)
        {
           mail->next = head1;
           mail = head1;
           p = head1;
           head1 = head1->next;
           p->next =NULL;
        }
        else
        {

          mail->next =head2;
          mail = head2;
          p = head2;
          head2 = head2->next;
          p->next =NULL;




        }
        }
        if(head1)
        {

            while(head1)
            {
                mail->next =head1;
                mail = head1;
                p = head1;
                head1 = head1->next;
                p->next = NULL;

            }
        }
        else if(head2)
        {
          while(head2)
          {
             mail->next =head2;
             mail = head2;
             p = head2;
             head2 = head2->next;
             p->next =NULL;
          }

    }

return tail;

}*/
void show(struct node*head)
{
     struct node*tail;
     tail =head;
     int top = 1;
     while(tail->next)
     {

           if(top)top=0;
           else printf(" ");
           printf("%d",tail->next->data);
           tail = tail->next;

     }

}
int main()
{

        int n,n1=0,n2=0;
        scanf("%d",&n);
        struct node*head1= (struct node*)malloc(sizeof(struct node));
        struct node*head2 = (struct node*)malloc(sizeof(struct node));
        struct node*head3 = (struct node*)malloc(sizeof(struct node));

        head1 = creat(head1,n);
         
        head1 =head1->next;
        head3->next = NULL;
        head2->next = NULL;
      struct node*tail1= head2;
        struct node*tail2=head3;

        while(head1)
        {
             if(head1->data%2==0)
             {
               tail1->next = head1;

              struct node*p;
               p  = head1;
                head1 = head1->next;
                p->next = NULL;
               tail1 = p;
               n1++;

             }
            else
            {
                tail2->next = head1;

                   struct node*p;
                p = head1;
                head1 = head1->next;
                p ->next =NULL;

                tail2 = p;
                n2++;
            }
       }
         cout<<n1<<" "<<n2<<endl;
         show(head2);
         cout<<endl;
         show(head3);
         cout<<endl;
         return 0;
        }







/***************************************************
User name: jk160505徐红博
Result: Accepted
Take time: 0ms
Take Memory: 148KB
Submit time: 2017-01-14 17:08:08
****************************************************/