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

/*
    Node element
*/
struct list{
	int value;
	struct list *next;
};

/*
    This function generates a list backwards
*/

struct list* generateList(){
    struct list *node, *previous_node;
    int size;

    printf("How many elements do you want to insert in the list? \n");
    scanf("%d", &size);

    if (size <= 0) return NULL;                                         //If the user requests an empty or negative list we return NULL

    for (int i = 0; i < size; i++){                                     //repeat as many times as the user requested
        node = malloc(sizeof(struct list));                             //we allocate memory for a new node
        (i == 0) ? (node->next =  NULL) : (node->next = previous_node); //if it's the first node the next value becomes NULL, otherwise it's assigned the address of the next node;
        printf("Enter value: %d\n", i);                                 //requesting and assigning an int to the value of the node
        scanf("%d", &(node->value));
        previous_node = node;                                           //a temporary variable used to store the memory of this node for the next iteration, it becomes the .next value
    }

    return node;
};

/*
    This function removes a node by finding the previous one (it never needs to remove the first node
    due to the problems nature), stores the soon to be removed node in a variable, bypasses it, and removes it from the memory
*/

void removeNode(struct list* head, int index){
    struct list* tmp;

    for (int i = 0; i < index-1; i++){                               //Finding the previous node
        head = head->next;
    }

    tmp = head->next;                                                //To be removed node

    head->next = head->next->next;                                   //We bypass it
    free(tmp);                                                       //Clearing the memory
}

/*
    This function is the solution to the problem, I wrote it at 5 A.M. I just got it working,
    I'm now trying to add comments, let's see what I can do, it's a miracle it's working,
    I'm not really sure how it manages to work at some parts.
*/
struct list * removeDupl_and_PushBack(struct list * head, int number){
    /*
    Index: We will use it to store at what part of the list we are, later on it will also be used to express the length of the list
    Found: Boolean, it becomes one if we have found at least one of the requested number
    First_index: The index of the first appearance of the wanted number in the list
    Removed: Boolean, becomes true if we have removed a node in the current iteration
    */
    int index = 0, found = 0, first_index = 0,removed = 0;
    /*
    tmp: Usually used to iterate through the list
    tmp_2: Usually to store necessary nodes of various reasons
    */
    struct list *tmp = head, *tmp_2;


    /*
        This block of code, finds all the duplicates, removes them, stores the index
        of the first appearance, side-effect: fetches the length of the list
    */
    while (tmp != NULL){                                            //Iterating through the list
        if (tmp->value == number){                                  //If we find the wanted number
            if(found == 0){                                         //For the first time
                found = 1;                                          //We store that we have found it
                first_index = index;                                //And store it's position
            }
            else{                                                   //If it's not the first time
                tmp = tmp->next;                                    //We move to the next node
                removeNode(head, index--);                          //And remove it
                removed = 1;                                        //We store that we have removed a node this iteration
                printf("Removed node at position: %d\n", index+1);
            }
        }
        index++;
        if (!removed) tmp = tmp->next;                              //We move to the next element only if we haven't removed anything (the move was executed previously)
        removed = 0;                                                //Re-initialize the removed var
    }

    tmp = head;
    tmp_2 = head;
    if(found == 1){                                                   //Only if we have found the requested number do we execute this code
        if (first_index == --index ){
            return head;                                              //If the wanted number is the last of the list, we return the list as is
            printf("Number was last already.\n");
        }
        else{
            if(first_index == 0){                                     //If it's the first number
                while(tmp->next != NULL){                             //We find the last node
                    tmp = tmp->next;
                }
                tmp->next = tmp_2;                                    //We set the new last node to the first one
                head = head->next;                                    //We set the second node as the head
                tmp_2->next=NULL;                                     //Last node points now to NULL
                printf("Number was first, moved to last.\n");
                return head;                                          //We return the new head
            }else{                                                    //If it's not the first node
                for (int i = 0; i < first_index-1; i++){              //We find the node previous to the requested
                    tmp = tmp->next;
                }
                tmp_2 = tmp->next;                                    //We store the requested node
                tmp->next = tmp->next->next;                          //We bypass it
                tmp = head;
                while(tmp->next != NULL){                             //We find the last node
                    tmp = tmp->next;
                }
                tmp->next = tmp_2;                                    //We point it to the requested node
                tmp_2->next=NULL;                                     //The last node now points to NULL
                printf("Number was at position: %d, moved to last.\n", first_index);
                return head;                                          //Returning the list
            }
        }
    }

    return head;
};

/*
    Function used to print all the elements of a list
*/

void printList(struct list* head){
    if (head == NULL){
        printf("Nothing to print");
        return ;
    }

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


int main()
{
    int number;

    struct list* head;
    if((head = generateList()) == NULL) return 0;                       //We assign head the address of the first node of the list, if it's NULL we terminate the program.
    printList(head);
    printf("Give the wanted number: ");
    scanf("%d", &number);
    head = removeDupl_and_PushBack(head, number);
    printList(head);
    return 0;
}