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

// Define a structure for the singly linked list node
struct Node {
    int data;
    struct Node* next;
};

// Function to insert a new node between two nodes
void insertBetween(struct Node* prevNode, int newData) {
    if (prevNode == NULL) {
        printf("Previous node cannot be NULL.\n");
        return;
    }

    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = newData;
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

// Function to display the linked list
void displayList(struct Node* head) {
    struct Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head = NULL;
    int data, position;

    printf("Enter the number of nodes: ");
    int numNodes;
    scanf("%d", &numNodes);

    if (numNodes <= 0) {
        printf("Invalid number of nodes.\n");
        return 1;
    }

    // Build the linked list based on user input
    printf("Enter data for node 1: ");
    scanf("%d", &data);
    head = (struct Node*)malloc(sizeof(struct Node));
    head->data = data;
    head->next = NULL;

    struct Node *current = head;
    for (int i = 2; i <= numNodes; i++) {
        printf("Enter data for node %d: ", i);
        scanf("%d", &data);
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = data;
        newNode->next = NULL;
        current->next = newNode;
        current = newNode;
    }

    printf("Original Linked List: ");
    displayList(head);

    // Take user input for the data and position of the new node
    printf("Enter data for the new node: ");
    scanf("%d", &data);
    printf("Enter the position to insert the new node (0-based index): ");
    scanf("%d", &position);

    // Insert the new node between two nodes
    if (position < 0 || position >= numNodes) {
        printf("Invalid position.\n");
    } else if (position == 0) {
        // Insert at the beginning
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = data;
        newNode->next = head;
        head = newNode;
    } else {
        struct Node* current = head;
        for (int i = 0; i < position - 1; i++) {
            current = current->next;
        }
        //fUNCTION FOR INSERT IN BETWEEN
        
        insertBetween(current, data);
    }

    printf("Updated Linked List: ");
    displayList(head);

    // Free memory for the linked list nodes
    current = head;
    while (current != NULL) {
        struct Node* temp = current;
        current = current->next;
        free(temp);
    }

    return 0;
}