4+5 Advanced C Ass. 1

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

typedef struct Node
{
    int value;
    struct Node* next;
} node;

node* create_node(int data)
{
    node* temp = (node*)malloc(sizeof(node));

    temp->value = data;
    temp->next = NULL;

    return temp;
}

void insert(node** head, int value)
{
    node* link = create_node(value);

    if (*head == NULL)
    {
        *head = link;
        return;
    }

    node* temp = *head;

    while (temp->next != NULL)
    {
        temp = temp->next;
    }

    temp->next = link;
}

void print_list(node* head)
{
    node* temp = head;

    if (head == NULL)
    {
        printf("List is empty.\n");
        return;
    }

    while (temp != NULL)
    {
        printf("%d-> ", temp->value);
        temp = temp->next;
    }
    printf("\n");
}

void delete_after(node* temp)
{
    node* delete_node = temp->next;
    temp->next = temp->next->next;
    free(delete_node);
}

void delete_head(node** head)
{
    if ((*head) && (*head)->next == NULL)
    {
        free(*head);
        return;
    }

    node* delete_node = *head;
    *head = (*head)->next;
    free(delete_node);
}

node* createList(node** head)
{
    node* temp = *head;
    node* head2 = NULL;
    node* new_node;

    if (*head == NULL) // no items
    {
        return head2;
    }

    if (*head && (*head)->next == NULL) // 1 item in the list
    {
        insert(&head2, (*head)->value);
        delete_head(head);
        return head2;
    }

    if (temp->value > temp->next->value) // first item bigger
    {
        insert(&head2, (*head)->value);
        delete_head(head);
        temp = *head;
    }

    while (temp->next->next != NULL && temp->next != NULL)
    {
        if (temp->value < temp->next->value && temp->next->value > temp->next->next->value)
        {
            insert(&head2, temp->next->value);
            delete_after(temp);
        }

        if(temp->next)
            temp = temp->next;
    }

    if (temp->next->value > temp->value) // last item
    {
        insert(&head2, temp->next->value);
        delete_after(temp);
    }

    return head2;
}

node* createList2(node** head) // second without memory allocation and free
{
    node* temp = *head;
    node* head2 = NULL;
    node* new_node;
    node* temp2;


    if (*head == NULL) // no items
    {
        return head2;
    }

    if (*head && (*head)->next == NULL) // 1 item in the list
    {
        head2 = *head;
        return head2;
    }


    // look for head

    if (temp->value > temp->next->value) // first item bigger
    {
        head2 = temp;
        temp2 = head2;
        temp = temp->next;
        temp2->next = NULL;
    }


    if (head2 == NULL)
    {
        while (temp->next->next != NULL && temp->next != NULL)
        {
            if (temp->value < temp->next->value && temp->next->value > temp->next->next->value)
            {
                head2 = temp->next;
                temp->next = temp->next->next;
                break;
            }

            else temp = temp->next;
        }
    }


    if (head2 == NULL) // no head found
        return head2;

    else // head2 is not empty
    {
        temp2 = head2; // to not lose head2

        if (temp->next) // after search for head
            temp = temp->next;

        else // if next node is null
            return head2;


        while (temp->next->next != NULL && temp->next != NULL) // start algorithm
        {
            if (temp->value < temp->next->value && temp->next->value > temp->next->next->value) // success finding
            {
                temp2->next = temp->next;
                temp2 = temp2->next;
                temp->next = temp->next->next;
                temp2->next = NULL; // very important!! disconnect from next node
            }

            if (temp->next)
                temp = temp->next;
        }

        if (temp->next->value > temp->value) // last item
        {
            temp2->next = temp->next;
            temp2 = temp2->next;
            temp->next = temp->next->next;
            temp2->next = NULL;
        }
    }

    return head2;
}

void main()
{
    node* head = NULL;

    insert(&head, 3);
    insert(&head, 6);
    insert(&head, 1);
    insert(&head, 9);
    insert(&head, 8);
    insert(&head, 4);
    insert(&head, 5);

    print_list(head);

    node* temp = head;

    node* head2 = createList2(&head);

    print_list(head2);
    print_list(head);
}