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

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

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

// Function to delete the nth node in the linked list
void deleteNthNode(struct Node** head, int n) {
    if (*head == NULL) {// Empty linked list
        return;
    }

    // To handle the case of deleting the first node
    if (n == 1) {
        *head = (*head)->next;
        return;
    }

    struct Node* prev = NULL;
    struct Node* current = *head;
    int count = 1;

    while (current != NULL) {//code from here skip if and goes down 1st
        if (count == n) {// Found the nth node, link the previous node to the next node of the current node
            prev->next = current->next;//main where we skip the node
            free(current);
            return;
        }

        // Move to the next node
        prev = current;//1st code comes here then if condition
        current = current->next;//updating the next value
        count++;
    }
}

// Function to append a new node with the given data to the end of the linked list
void appendNode(struct Node** head, int data) {
    // Create a new node and set its data and next pointer
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;

    // If the linked list is empty, make the new node the head
    if (*head == NULL) {//*head because **head!!
        *head = newNode;
        return;//imp
    }

    // Traverse the linked list to find the last node
    struct Node* last = *head;//*head because **head!!
    while (last->next != NULL) {
        last = last->next;//here we will get last value//append value till last
    }

    // Append the new node to the end of the linked list
    last->next = newNode;//link the last value to new value
}


// Function to free the memory used by the linked list
void freeLinkedList(struct Node* head) {
    struct Node* temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }
}

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

    // Adding elements to the linked list
    appendNode(&head, 1);
    appendNode(&head, 2);
    appendNode(&head, 3);
    appendNode(&head, 4);
    appendNode(&head, 5);

    printf("Original linked list: ");
    printLinkedList(head);

    int n = 3; // Delete the 3rd node (indexing starts from 1)
    deleteNthNode(&head, n);

    printf("Linked list after deleting the %dth node: ", n);
    printLinkedList(head);

    // Free memory used by the linked list
    freeLinkedList(head);

    return 0;
}