// linked list -> Delete a node at nth position

#define _CRT_SECURE_NO_WARNINGS
#include "stdio.h"
#include "stdlib.h"

struct Node {
    int data;
    struct Node* next;
};

struct Node* head;

void Insert(int data) {                                         // insert in the end of the list
    struct Node* temp1 = malloc(sizeof(struct Node));           //alloc memory for a new node
    temp1->data = data;                                         //the new node will contain the data that we asked to store
    temp1->next = NULL;                                         //and for now we assume that this is the last node, so it points to NULL
    if (head == NULL) {                                         // head == NULL means the the list is empty now
        head = temp1;                                           // so we have to tell to our list that the head is the node that we have just inserted
    }
    else {
        struct Node* temp2 = head;                              // if the list was no empty, create a new node that store the start of our list
        while (temp2->next != NULL) {                           //search for the end of the list by controlling if the next node is NULL,
            temp2 = temp2->next;                                //if the next adress is NULL it means that the list is ended.
        }
        temp2->next = temp1;                                    //whem we found the last node, we have to put there the adress of our node that we want to insert
        temp1->next = NULL;                                     // of course the last node have to point to NULL
    }

}
void Print() {
    struct Node* temp = head;                   //it's the beginning of the list
    printf("list is : ");
    while (temp != NULL) {                      //while list is not end
        printf("%d  ", temp->data);             //print the data of the node
        temp = temp->next;                      //go to the next node
    }
    printf("\n");
}

void Delete(int n) {
    struct Node* temp1 = head;

    if (n == 1) {                               //if we have to delete the first node of the list
        head = temp1->next;                     //we had to tell that the new head is the second node of the list
        free(temp1);                            //next we have to dealocate the memory of the deleted node
        return;
    }
    int i;
    for (i = 0; i < n - 2;i++) {                //if the node to delete isn't on the first place,we have to scroll the list until we find the right nth position
        temp1 = temp1->next;

        struct Node* temp2 = temp1->next;       //save the adress of the node to delete
        temp1->next = temp2->next;              //put the adress of the node after the one to delete in the adress of the node to delete
        free(temp2);                            // free the memory of the deleted node
    }


}

int main() {

    head = NULL; // at this stage the list is empty
    Insert(2);
    Insert(4);
    Insert(6);
    Insert(5);      // insert at the end of the list -> List : 2,4,6,5
    Print();
    int n;
    printf("enter a position\n");
    scanf("%d", &n);                // store in n the position where to delete the node
    Delete(n);
    Print();

 }