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

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

// Linked list structure
struct LinkedList {
    struct Node* head;
};

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to insert a node at the end of the circular linked list
void insertAtEnd(struct LinkedList* list, int data) {
    struct Node* newNode = createNode(data);
    if (list->head == NULL) {
        list->head = newNode;
        newNode->next = newNode; // Point to itself to make it circular
        return;
    }
    struct Node* temp = list->head;
    while (temp->next != list->head) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->next = list->head;
}

// Function to delete a node with given value from the circular linked list
void deleteNode(struct LinkedList* list, int key) {
    if (list->head == NULL) return;

    struct Node *current = list->head, *prev = NULL;
    while (current->data != key) {
        if (current->next == list->head) {
            printf("Node with value %d not found\n", key);
            return;
        }
        prev = current;
        current = current->next;
    }

    // If the node to be deleted is the only node in the list
    if (current->next == list->head && prev == NULL) {
        free(current);
        list->head = NULL;
        return;
    }

    // If the list has more than one node
    if (current == list->head) {
        prev = list->head;
        while (prev->next != list->head)
            prev = prev->next;
        list->head = current->next;
        prev->next = list->head;
        free(current);
    } else if (current->next == list->head) {
        prev->next = list->head;
        free(current);
    } else {
        prev->next = current->next;
        free(current);
    }
}

// Function to display the circular linked list
void display(struct LinkedList* list) {
    if (list->head == NULL) {
        printf("List is empty\n");
        return;
    }
    struct Node* temp = list->head;
    do {
        printf("%d ", temp->data);
        temp = temp->next;
    } while (temp != list->head);
    printf("\n");
}

int main() {
    struct LinkedList ll;
    ll.head = NULL;

    // Insert nodes
    insertAtEnd(&ll, 1);
    insertAtEnd(&ll, 2);
    insertAtEnd(&ll, 3);
    insertAtEnd(&ll, 4);

    printf("Original List:\n");
    display(&ll);

    // Delete node
    deleteNode(&ll, 3);
    printf("List after deleting node with value 3:\n");
    display(&ll);

    return 0;
}