#include <iostream>
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
void deleteNode(Node*& head, int key) {
if (head == nullptr)
return;
if (head->data == key) {
Node* temp = head;
head = head->next;
delete temp;
return;
}
Node* current = head;
Node* prev = nullptr;
while (current != nullptr && current->data != key) {
prev = current;
current = current->next;
}
if (current == nullptr)
return;
prev->next = current->next;
delete current;
}
void printList(Node* head) {
while (head != nullptr) {
std::cout << head->data << " ";
head = head->next;
}
std::cout << std::endl;
}
int main() {
Node* head = new Node(1);
head->next = new Node(2);
head->next->next = new Node(3);
head->next->next->next = new Node(4);
std::cout << "Original List: ";
printList(head);
int key = 3;
deleteNode(head, key);
std::cout << "List after deleting node with key " << key << ": ";
printList(head);
return 0;
}