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

#define Malloc(n, type) (type *)malloc((unsigned)((n) * sizeof(type)))
#define Realloc(ptr, n, type) (type *)realloc(ptr, (n) * sizeof(type))

typedef struct Node
{
    int key;
    struct Node *next;
    struct Node *down;
} Node;

typedef struct
{
    int level;
    struct Node *header;
} skiplist;

int level()
{
    /*
    This function takes the coin flip and decides the level of the node with each
    level having a probability of 0.25.

    arg: void
    return: a number from the set {1,2,3, 4}
    */
    int level = 1;
    for (int i = 0; i < 3; i  )
    {
        unsigned int coin = (unsigned int)rand();
        coin = coin % 2;
        if (coin)
        {
            level  ;
        }
        else
            break;
    }
    return level;
}

skiplist skip_list_init();

Node *Traverse_Express(Node *, int);

Node *skip_list_search(skiplist, int);

Node *insert_level(Node *, int, int, int);

void skip_list_insert(skiplist *, int);

void skip_print(skiplist);

int main()
{
    srand(time(0));
    int arr[10000];
    for (int i = 0; i < 10; i  )
    {
        arr[i] = (int)rand();
    }
    printf("The array is initialised\n");
    skiplist list;
    list = skip_list_init();
    printf("The Skip list is initialised\n");
    if (list.header == NULL)
    {
        printf("List is null\n");
    }
    for (int i = 0; i < 10; i  )
    {
        skip_list_insert(&list, arr[i]);
        printf("The %d element is initialised with key: %d\n", i, arr[i]);
    }
    printf("The skip list is:\n");
    skip_print(list);
    return 0;
}

void skip_print(skiplist list)
{
    /*
    The function prints the skip list level-wise.

    arg: list
    return: none
    */
    Node *temp = list.header;
    int count = 0;
    for (int i = list.level; i > 0; i--)
    {
        printf("The Keys at level %d:\n", i);
        while (NULL != temp->next)
        {
            printf("%d ->", temp->key);
            temp = temp->next;
        }
        printf("%d\n", temp->key);
        int dummy = count;
        temp = list.header;
        while (dummy)
        {
            temp = temp->down;
            dummy--;
        }
        count  ;
    }
}

skiplist skip_list_init()
{
    /*
    This function creates the first node in the skip list with key value
    to be negative infinity and level of the list =1.

    arg: None
    return: Skiplist initialised with a Node having key as INT_MIN.
    */
    skiplist list;
    Node *head;
    if (NULL == (head = Malloc(1, Node)))
    {
        exit(1);
    }
    list.header = head;
    list.level = 1;
    head->key = INT_MIN;
    head->next = NULL;
    head->down = NULL;
    return list;
}

Node *skip_list_search(skiplist list, int key)
{
    /*
    The function returns a pointer to the either the key itself if present
    or the key immediatedly smaller than the searched key.

    arg:
        list:The skiplist to be searched. Type: skiplist
        key: A key to be searched. Type: int.
    return: Type: Node pointer
        A pointer to the searched key or immediately smaller it.
    */
    if (list.header == NULL)
        exit(1);
    else
        skip_print(list);

    int level = list.level; // Number of levels already present in the list
    Node *curr = list.header;
    printf("Inside Skip search\n");
    printf("The value of level %d\n", level);
    for (; level > 0; level--)
    {
        curr = Traverse_Express(curr, key);
        if ((curr->key == key) && (INT_MIN != curr->key))
        {
            return curr;
        }
        if (NULL != curr->down)
            curr = curr->down;
    }
    printf("The value at current node %d\n", curr->key);
    printf("Leaving Skip_search\n");
    return curr;
}

Node *Traverse_Express(Node *temp, int key)
{
    printf("On the express way\n");
    printf("We are searching the key: %d\n", key);
    while (key > temp->key && NULL != temp->next)
    {
        printf("Loop of expressway\n");
        printf("The current key : %d\n", temp->key);
        if (key >= temp->next->key)
            temp = temp->next;
        else
            break;
    }
    printf("Left the express way\n");
    return temp;
}

Node *insert_level(Node *nod, int key, int lev, int list_lev)
{
    /*
    Inserting the key till the required level

    arg:
        nod: a pointer to the exsiting skip list
        key: key to be inserted
        lev: the level of the key
        list_lev: the number of levels in the given skiplist

    return: A Node pointer to the head of the skiplist with the key 
            inserted to the existing list.
    */
    Node *temp1 = nod, *temp3 = NULL;
    printf("\nStarting of insert at level procedure\n");
    // Procedure to cut-off the extra levels in the list if any
    if (lev < list_lev)
    {
        for (int i = list_lev - lev; i > 0; i--)
        {
            printf("Searching on the level: %d\n", i   lev);
            temp1 = Traverse_Express(temp1, key);
            temp1 = temp1->down;
        }
    }
    printf("The value of first node: %d\n", temp1->key);
    // Procedure to insert from the required level till level 1
    for (int i = 0; i < lev; i  )
    {
        Node *temp2 = Malloc(1, Node);
        temp2->key = key;
        temp2->next = NULL;
        temp2->down = NULL;
        temp1 = Traverse_Express(temp1, key);
        printf("Temp1 current key:%d\n", temp1->key);
        if (NULL == temp1->next)
        {
            temp1->next = temp2;
            printf("Node inserted at level: %d\n", lev - i);
        }
        else
        {
            printf("Entered the else procedure\n");
            temp2->next = temp1->next;
            temp1->next = temp2;
            printf("%d\n", temp1->next->key);
        }
        if (i > 0)
        {
            temp3->down = temp2;
        }
        temp1 = temp1->down;
        temp3 = temp2;
        /*
        free(temp2);
        if(temp3==NULL)
        {
            printf("did a fuck up\n");
            exit(1);
        }*/
    }
    skiplist list;
    // list = skip_list_init(list);
    list.header = nod;
    list.level = list_lev;
    printf("Printing skip list from insert level\n");
    skip_print(list);
    printf("End insert level procedure\n\n\n");
    temp1 = temp3 = NULL;
    return nod;
    free(temp1);
    free(temp3);
}

void skip_list_insert(skiplist *list, int key)
{
    /*
    This function finds the key value and if already present, then returns back
    else it inserts the key at its right place.

    arg: a skilplist by reference and a key
    return: None
    */
    printf("Inside skip_list_insert\n");
    Node *req = skip_list_search(*list, key);
    printf("The value returned by skip search %d\n", req->key);
    if (key == req->key)
    {
        printf("Key %d is already present in skip list\n", key);
    }
    Node *temp1 = list->header;
    int list_lev = list->level;
    printf("The list level = %d\n", list_lev);
    int lev = level();
    printf("The prob level %d\n", lev);
    Node *hold_prev = NULL;
    // creating a skip list if level returned is greater than existing one.
    if (lev > list_lev)
    {
        for (int i = lev - list_lev; i > 0; i--)
        {
            skiplist l = skip_list_init();
            Node *inser = Malloc(1, Node);
            printf("The value of i in loop %d\n", i);
            inser->key = key;
            inser->down = NULL;
            inser->next = NULL;
            l.header->next = inser;
            Node *trans = l.header;
            // Zipping the previous levels with new level
            while (NULL != hold_prev)
            {
                trans->down = hold_prev;
                trans = trans->next;
                hold_prev = hold_prev->next;
            }
            hold_prev = l.header;
            l.header = NULL;
            if (hold_prev == NULL)
            {
                printf("Big Mistake");
                exit(1);
            }
            else
            {
                printf("You are doing it correct way\n");
            }
        }
        list->header = hold_prev;
        list->level = lev - list_lev;
        skip_print(*list);
        // Returning a pointer to the zeroth element of last level in this list.
        while (NULL != hold_prev->down)
        {
            hold_prev = hold_prev->down;
        }
    }
    // Inserting the node till the min(list_lev, level())
    if (list_lev > lev)
    {
        temp1 = insert_level(temp1, key, lev, list_lev);
    }
    else
    {
        temp1 = insert_level(temp1, key, list_lev, list_lev);
    }
    skiplist l1 = skip_list_init();
    l1.header = temp1;
    l1.level = list_lev;
    skip_print(l1);

    printf("\n Now the Zipping procedure with level()>list_lev starts\n");
    // Zipping Procedure only if level()>list_lev
    if (lev > list_lev)
    {
        hold_prev->down = temp1;
        skiplist l1 = skip_list_init();
        l1.header = list->header;
        l1.level = lev;
        skip_print(l1);
        printf("the key at the first node:%d\n", temp1->key);
        hold_prev = hold_prev->next;
        while (temp1->key != key)
        {
            temp1 = temp1->next;
            printf("Zipping over keys:\n");
            printf("Current key: %d\n", temp1->key);
        }
        hold_prev->down = temp1;
        list->level = lev;
    }
    if (list_lev > lev)
    {
        list->level = list_lev;
    }
    printf("\n\n\n");
}

The above is my implementation. I have tried with all my might to debug the code but I am falling to implement a skip list for past 1 month. I genuinely request with pleading hands