#include <stdio.h>
#include <stdlib.h>


typedef struct node{
    int data;
    struct node *prev, *next;
}node;

void push(node** headRef,int d){
    struct node* newNode=(node*) malloc(sizeof(node));
    newNode->data=d;
    newNode->next=*headRef;
    newNode->prev=NULL;
    if (*headRef)
        (*headRef)->prev=newNode;
    *headRef=newNode;
}

void print(node *h){
    printf("\nList : ");
    while(h){
        printf("%d ",h->data);
        h=h->next;
    }
}

void printDoubly(node *h){
    node* last=h;
    printf("\nList Forward:\n");
    while(h){
        printf("%d ",h->data);
        last=h;
        h=h->next;
    }
    printf("\nBackward:\n");
    for(;last;last=last->prev)
        printf("%d ",last->data);
}
void reverse (node** headRef){
    
    //insert your solution here
    
}

node * merge(node*h1, node*h2){
    node *head=NULL;
    
    //insert your solution here
    
    
    return head;
}

void clean(node* head){

    //insert your solution here

}
void reverseTest(){
    int list[]={1,5,9,3},i;
    node *head=NULL;
    for(i=sizeof(list)/sizeof(int)-1;i>=0;i--)
        push(&head,list[i]);
    print(head);
    reverse(&head);
    print(head);
    printDoubly(head);

}

void mergeTest(){
    int t1[]={1,3,4,6}, t2[]={0,
        2,5,5,7},i;
    node *head1=NULL, *head2=NULL, *head=NULL;
    
    //create the lists:
    for(i=sizeof(t1)/sizeof(int)-1;i>=0;i--){
        push(&head1, t1[i]);
    }
    
    for(i=sizeof(t2)/sizeof(int)-1;i>=0;i--){
        push(&head2, t2[i]);
    }
    
    print(head1);
    print(head2);
    head=merge(head1,head2);
    print(head);
    printDoubly(head);

}

void cleanTest(){
    int list[]={1,5,9,5,1,3,3,1,1},i;
    node *head=NULL;
    for(i=sizeof(list)/sizeof(int)-1;i>=0;i--)
        push(&head,list[i]);
    print(head);
    clean(head);
    print(head);
    printDoubly(head);

}

int main(void){
    //mergeTest();
    
    //reverseTest();
    
    cleanTest();
    
    getchar();
    return 0;
}