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

struct node
{
    int Data;
    struct node* Next;
};

struct node* MakeEmpty(struct node* L)
{
    if(L != NULL)
        DeleteList( L );
    L = (struct node*)malloc(sizeof(struct node));

    if(L == NULL)
        printf("Out of memory!\n");

    L->Next = NULL;
    return L;
}

int IsEmpty(struct node* L)
{
    return L->Next == NULL;
}
int IsLast(struct node* P, struct node* L)
{
    return P->Next == NULL;
}

struct node* Find(int X, struct node* L)
{
    struct node* P;
    P = L->Next;

    while(P != NULL && P->Data != X)
        P =P->Next;

    return P;
}

struct node* FindPrevious(int X, struct node* L)
{
    struct node* P;
    P = L;

    while(P->Next != NULL && P->Next->Data != X)
        P = P->Next;

    return P;
}

void Delete(int X, struct node* L)
{
    struct node *P, *temp;
    P = FindPrevious(X, L);

    if( !IsLast(P, L) )
    {
        temp = P->Next;
        P->Next = temp->Next; //bypass delete cell
        free(temp);
    }
}

void Insert(int X, struct node* L, struct node* P)
{
    struct node* temp;
    temp = (struct node*)malloc(sizeof(struct node));
    temp->Data = X;
    temp->Next = P->Next;
    P->Next = temp;
}

void InsertLast(int X, struct node* L)
{
    struct node* temp, *P=L;

    temp = (struct node*)malloc(sizeof(struct node));
    temp->Data = X;

    while(P->Next != NULL)
        P=P->Next;

    P->Next = temp;

    temp->Next = NULL;

}

void PrintList(struct node* L)
{
    struct node* P = L;
    if( IsEmpty(L))
        printf("Empty list\n");
    else
        do
        {
            P=P->Next;
            printf("%d\t", P->Data);
        }
        while( !IsLast(P, L) );
    printf("\n");
}

void DeleteList(struct node* L)
{
    struct node *P, *temp;
    P = L->Next;
    L->Next = NULL;

    while(P != NULL)
    {
        temp = P->Next;
        free(P);
        P=temp;
    }
}

int size( struct node* L)
{
    struct node* p = L->Next;
    int count = 0;
    while(p != NULL )
    {
        count += 1;
        p = p->Next;
    }
    return count;
}

void Concatenate(struct node** L1, struct node** L2)
{
    if( *L1 == NULL )
    {
        *L1 = *L2;

        //return L2;
    }
    else
    {
        //iterate to the end of L1
        struct node* temp = *L1;

        while(temp->Next != NULL)
            temp = temp->Next;

        temp->Next = (*L2)->Next;
    }
}


int main()
{
    struct node* L1;
    L1 = MakeEmpty(NULL);

    //printf("%d", L1 == NULL);

    Insert(1, L1, L1);
    PrintList(L1);
    Insert(2, L1, L1);
    PrintList(L1);
    Insert(3, L1, L1);
    PrintList(L1);
    Insert(4, L1, L1);
    PrintList(L1);
    Insert(5, L1, L1);
    PrintList(L1);

    InsertLast(100, L1);
    PrintList(L1);
    InsertLast(200, L1);
    PrintList(L1);

    struct node* p = Find(4, L1);

    if(p!=NULL)
    {
        printf("Found: %d\n", p->Data);
    }

    Delete(4, L1);
    PrintList(L1);

    struct node* L2;
    L2=MakeEmpty(NULL);

    printf("The second list...\n");
    InsertLast(111, L2);
    InsertLast(222, L2);
    InsertLast(333, L2);
    PrintList(L2);

    //concatenate
    Concatenate(&L1, &L2);

    printf("After concatenation...\n");
    PrintList(L1);

    Delete(222, L2);
    PrintList(L1);



    DeleteList(L1);
    DeleteList(L2);
    return 0;
}