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


struct TNode
{
     int data;
     struct TNode *next;
     struct TNode *prev;  
};

struct TList
{
    struct TNode *head;
    struct TNode *tail;   
};

void ListInit(struct TList *L)
{
     (*L).head = NULL;
     (*L).tail = NULL;
}

int ListIsEmpty(struct TList L)
{
   return (L.head == NULL);  
}

void ListDisplayForward(struct TList L)
{
     int counter = 0;
     struct TNode *curr = L.head;
     printf("List (head-->tail): ");
     while(curr != NULL)
     {
         printf("%d -> ",curr->data);       
         curr = curr->next;
         counter++;       
     }
     printf("NULL \n");
     printf("Liczba wezlow listy : %d \n",counter);
}

void ListDisplayBackward(struct TList L)
{
     int counter = 0;
     struct TNode *curr = L.tail;
     printf("List (tail-->head): ");
     while(curr != NULL)
     {
         printf("%d -> ",curr->data);       
         curr = curr->prev;
         counter++;       
     }
     printf("NULL \n");
     printf("Liczba wezlow listy : %d \n",counter);
}


void ListInsert(struct TList *L,int k)
{
    struct TNode *x = (struct TNode *)malloc(sizeof(struct TNode )) ;
    x->data = k;
    x->next = (*L).head;
    if((*L).head != NULL)
       (*L).head->prev = x;
    (*L).head = x;
    x->prev = NULL; 
    if(x->next == NULL)
        (*L).tail = x;      
}

void ListDelete(struct TList *L)
{
     struct TNode *x = (*L).head;
     if((*L).head != NULL)
     {
        if((*L).head->next == NULL)     
             (*L).tail = (*L).head->prev;              
         (*L).head = x->next;
         if(x->next != NULL)
            x->next->prev = x->prev;       
         free(x);    
     }
}

struct TNode *headdel(struct TNode **first,struct TNode **last)
{
    struct TNode *temp = (*first);
    if((*first) != NULL)
    {
        if((*first)->next == NULL)
            (*last) = NULL;
        else
            (*first)->next->prev = NULL;
        (*first) = (*first)->next;                       
    }
    return temp;  
}

void tailins(struct TNode *p,struct TNode **first,struct TNode **last)
{
     p->next = NULL;
     if((*first) == NULL)
     {
         p->prev = NULL;
         (*first) = p;        
     }
     else
     {
         (*last)->next = p;
         p->prev = (*last);
     }
     (*last) = p;
}

int ListSplit(struct TList L,struct TList *A,struct TList *B)
{
    int isEmptyB,swapLists;
    struct TNode *currNode,*prevNode;
    swapLists = 1;
    isEmptyB = 1;
    ListInit(A);
    ListInit(B);
    if(L.head != NULL)
    {        
        // Usun wezel z glowy listy L
        //Wstaw wezel za ogon listy A
        currNode = headdel(&L.head,&L.tail);
        tailins(currNode,&(*A).head,&(*A).tail);
        prevNode = currNode;
    }
    while(L.head != NULL)
    {
        // Usun wezel z glowy listy L
        currNode = headdel(&L.head,&L.tail);
        if(prevNode->data > currNode->data)
           swapLists = !swapLists;
        if(swapLists)
        {
           //Wstaw wezel za ogon listy A
           tailins(currNode,&(*A).head,&(*A).tail);
        }
        else
        {
            //Wstaw wezel za ogon listy B
            tailins(currNode,&(*B).head,&(*B).tail);
            isEmptyB = 0;
        }
        prevNode = currNode;                  
    }
    return isEmptyB;
}

void ListMerge(struct TList A,struct TList B,struct TList *L)
{
     struct TNode *tmpA = NULL;
     struct TNode *tmpB = NULL;
     struct TNode *poprzedniZtmpA = NULL;
     struct TNode *poprzedniZtmpB = NULL;
     int koniecSeriiWtmpA,koniecSeriiWtmpB;
     ListInit(L);
     if(A.head != NULL)
     {
         // Usun wezel z glowy listy A
         tmpA = headdel(&A.head,&A.tail);                      
     }
     if(B.head != NULL)
     {
         // Usun wezel z glowy listy B
         tmpB = headdel(&B.head,&B.tail);                    
     }
     koniecSeriiWtmpA = (tmpA == NULL);
     koniecSeriiWtmpB = (tmpB == NULL);
     while(A.head != NULL || B.head != NULL)
     {
           while(!koniecSeriiWtmpA && !koniecSeriiWtmpB)
               if(tmpA->data <= tmpB->data)
               {
                  // Wstaw wezel z listy A za ogon listy L
                  tailins(tmpA,&(*L).head,&(*L).tail);
                  poprzedniZtmpA = tmpA;
                 // Usun wezel z glowy listy A
                 tmpA = headdel(&A.head,&A.tail);     
                 if(poprzedniZtmpA == NULL || tmpA == NULL || poprzedniZtmpA->data > tmpA->data)
                      koniecSeriiWtmpA = 1;                                  
               }
               else
               {
                   // Wstaw wezel z listy B za ogon listy L
                   tailins(tmpB,&(*L).head,&(*L).tail);
                   poprzedniZtmpB = tmpB;
                   // Usun wezel z glowy listy B
                   tmpB = headdel(&B.head,&B.tail);
                   if(poprzedniZtmpB == NULL || tmpB == NULL || poprzedniZtmpB->data > tmpB->data)
                      koniecSeriiWtmpB = 1;
               }
            while(!koniecSeriiWtmpA)
            {
                // Wstaw wezel z listy A za ogon listy L
                tailins(tmpA,&(*L).head,&(*L).tail);
                 poprzedniZtmpA = tmpA;
               // Usun wezel z glowy listy A
                 tmpA = headdel(&A.head,&A.tail);
                 if(poprzedniZtmpA == NULL || tmpA==NULL || poprzedniZtmpA->data > tmpA->data)
                      koniecSeriiWtmpA = 1;
            }
            while(!koniecSeriiWtmpB)
            {
                // Wstaw wezel z listy B za ogon listy L
                tailins(tmpB,&(*L).head,&(*L).tail);
                poprzedniZtmpB = tmpB;
               // Usun wezel z glowy listy B
               tmpB = headdel(&B.head,&B.tail);
               if(poprzedniZtmpB == NULL || tmpB==NULL || poprzedniZtmpB->data > tmpB->data)
                   koniecSeriiWtmpB = 1;
            }
           koniecSeriiWtmpA = (tmpA == NULL);
           koniecSeriiWtmpB = (tmpB == NULL);
           poprzedniZtmpA = NULL;
           poprzedniZtmpB = NULL;                               
     }
}

int main()
{
    int k,n,m;
    struct TList L,L1,L2;
    ListInit(&L);
    srand(time(NULL));
    scanf("%d %d",&n,&m);
    for(k = 1;k <= n;k++)
        ListInsert(&L,rand()%m);
    printf("List L \n");
    ListDisplayForward(L);
    ListDisplayBackward(L);
    ListSplit(L,&L1,&L2);
   printf("List L1 \n");
    ListDisplayForward(L1);
    ListDisplayBackward(L1);
    printf("List L2 \n");
    ListDisplayForward(L2);
    ListDisplayBackward(L2);
    ListMerge(L1,L2,&L);
    printf("List L \n");
    ListDisplayForward(L);
    ListDisplayBackward(L);
    while(!ListIsEmpty(L))
      ListDelete(&L);                   
    system("PAUSE");
    return 0;
}