//insertion at nth position on the linked list

#define _CRT_SECURE_NO_WARNINGS

#include "stdlib.h"
#include "stdio.h"

struct Node {                   //define de Node struct
    int data;                   // it's composed of a part that contain the data of the current node and the adress of the next node
    struct Node* next;
};

struct Node* head;  // global variable so we can access from all the function

void Insert(int data, int n) {

    struct Node* temp1 = malloc(sizeof(struct Node*));              //dynamic alloc memory for a Node type
    temp1->data = data;                                             //store the data that we want on the data box of the struct
    temp1->next = NULL;                                             // in the adress of the next Node we put a Null adress so this will be the last element for now

    if (n == 1) {                           //if we want to place the number in the first place, we have to put the old head of the list as next node adress, so our insertion will be at the beginning
        temp1->next = head;
        head = temp1;                       //set the new inserted Node as head
        return;                             //and it's done
    }
struct  Node* temp2 = head;                     // else create a new node that contain the old head
for (int i = 0; i < n - 2; i++) {               //scroll all the node while the position is != of where we want to insert
    temp2 = temp2->next;
}
temp1->next = temp2->next;                      //when we found the position where to insert our temp1
temp2->next = temp1;

}

void Print() {
    struct Node* temp = head;               //start from the head, while the list is != empty print all the data
    while (temp != NULL) {
        printf("%d", temp->data);
        temp = temp->next;
    }
    printf("\n");
}


int main() {
    head = NULL;  // empty list
    Insert(1, 1);                       //insert the number 1 on the position 1 of the list
    Insert(2, 2);
    Insert(3, 3);
    Insert(4, 2);
    Print();
}