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

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

Node *head = NULL;

Node* createNode(int data) {
    Node *n = (Node*)malloc(sizeof(Node));
    n->data = data;
    n->next = NULL;
    return n;
}

void insertEnd(int data) {
    Node *n = createNode(data);

    if (head == NULL) {
        head = n;
        n->next = head;
        return;
    }

    Node *temp = head;
    while (temp->next != head) {
        temp = temp->next;
    }
    temp->next = n;
    n->next = head;
}

void deleteKey(int key) {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }

    Node *curr = head;
    Node *prev = NULL;

    if (head->data == key) {
        if (head->next == head) {
            free(head);
            head = NULL;
            return;
        }

        while (curr->next != head) {
            curr = curr->next;
        }
        curr->next = head->next;
        free(head);
        head = curr->next;
        return;
    }

    curr = head->next;
    prev = head;

    while (curr != head) {
        if (curr->data == key) {
            prev->next = curr->next;
            free(curr);
            return;
        }
        prev = curr;
        curr = curr->next;
    }

    printf("Key not found\n");
}

void display() {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }

    Node *temp = head;
    printf("CLL: ");
    do {
        printf("%d ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("\n");
}

int main() {
    int choice, value;

    while (1) {
        printf("\n--- CIRCULAR LINKED LIST MENU ---\n");
        printf("1. Insert at end\n");
        printf("2. Delete by key\n");
        printf("3. Display\n");
        printf("4. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);

        switch (choice) {
            case 1:
                printf("Enter value: ");
                scanf("%d", &value);
                insertEnd(value);
                break;
            case 2:
                printf("Enter key to delete: ");
                scanf("%d", &value);
                deleteKey(value);
                break;
            case 3:
                display();
                break;
            case 4:
                return 0;
            default:
                printf("Invalid choice\n");
        }
    }
}