// Danh Sách Liên Kết, Và tách DS làm 2 danh sách. 

#include<stdio.h>

#include<iostream.h>

typedef struct Node

{

    int info;

        Node *next;

};

typedef struct list  // khai bao 1 cau truc cua Node gom dau va duoi

{

    Node *h;

        Node *t;

};

void khoi_tao(list &b) // Gan cho gia tri dau va ket thuc node la NULL

{

    b.h=b.t=NULL;    

}

Node *tao_nut_moi (int x)   // Tao 1 nut moi

{

    Node *p=new Node;   // cap phat dong bo nho cho node

    if(!p) return p;

    p->info =x;         // Gia tri cua node =x

    p->next =NULL;      // Con tro den nut ke tiep gan gia tri la NULL

        return p;

}

void them_cuoi(list &N, int x) // Them 1 node vao cuoi cua danh sach 

{

    Node *p=tao_nut_moi(x);

    if(!p) return;

    if(!N.h) N.h=N.t=p;  // Neu DS chua co pt nao, thi dau = cuoi = p 

    else

    {

        N.t->next = p ;

                N.t =  p;

    }

}

void them_dau(list &N, int x) // Them 1 node vao dau cua danh sach

{

    Node *p=tao_nut_moi(x);

    if(!p) return;

    if(!N.h) N.h=N.t=p;  // Neu DS chua co pt nao, thi dau = cuoi = p 

    else

    {

        p->next = N.h ;

                N.h =  p;

    }

}

void tao_2ds (list N, list &a, list &b)

{

    khoi_tao(a);  // Khoi tao 2 DS a,b de luu tru ds chan va le

    khoi_tao(b);

    for(Node *p=N.h; p; p=p->next)

    {

        if((p->info)%2!=0)  // neu ko chia het cho 2

            them_cuoi(a,p->info); // cho vao mang a

        else                // nguoc lai chia het cho 2

            them_cuoi(b,p->info); // cho vao mang b

    } 

}

void xuat_ds(list N)

{

    for(Node *p=N.h; p; p=p->next)        // Xuat Danh Sach LK

            cout << "  "<< p->info << " "; 

}

void main()

{

    int x, i=0;

    list N,a,b;

    do

    {

        cout << "Nhap " << ++i << " :" ;

        cin >> x;

                them_cuoi(N,x);

    }

    while(x!=0);

        cout << "Gia Tri Vua Nhap : ";

        tao_2ds(N,a,b);

    xuat_ds(N);

    cout << "

Gia Tri Le : ";

    xuat_ds(a);

    cout << "

Gia Tri Chan : ";

    xuat_ds(b);

    tao_2ds1(N,a,b);

    cout << "

Gia Tri Le : ";

    xuat_ds(a);

    cout << "

Gia Tri Chan : ";

    xuat_ds(b);

}