We are given the head of a linked list and a key. We have to delete the node that contains this given key. The following two examples elaborate on this problem further.
LinkedListNode* delete_node(LinkedListNode* head,int key) {//TODO: Write - Your - Codereturn head;}
LinkedListNode* delete_node(LinkedListNode* head,int key) {LinkedListNode* prev = nullptr;LinkedListNode* current = head;while (current != nullptr) {if (current->data == key) {if(current == head){head = head->next;delete current;current = head;}else{prev->next = current->next;delete current;current = prev->next;}}else{prev = current;current = current->next;}}// key not found in listif (current == nullptr) {return head;}return head;}int main(int argc, char* argv[]) {LinkedListNode* list_head = nullptr;list_head = LinkedList::create_random_list(10);printf("Original: ");LinkedList::display(list_head);vector<int> lst = LinkedList::to_list(list_head);printf("\nDeleting %d",lst.at(5));list_head = delete_node(list_head, lst.at(5));printf("\nAfter Delete Node:");LinkedList::display(list_head);printf("\nDeleting (Non-Existing) %d", 101);list_head = delete_node(list_head, 101);printf("\nAfter Delete Node:");LinkedList::display(list_head);printf("\nDeleting 1st node:%d", lst.at(0));list_head = delete_node(list_head, lst.at(0));printf("\nAfter Delete 1st Node:");LinkedList::display(list_head);lst = LinkedList::to_list(list_head);printf("\nDeleting last node: %d" , lst.at(lst.size() - 1));list_head = delete_node(list_head, lst.at(lst.size() - 1));printf("\nAfter Delete last Node:");LinkedList::display(list_head);}
Linear, O(n)
Constant, O(1)
First, we have to find the key in the linked list. We’ll keep two pointers, current and previous, as we iterate the linked list.
If the key is found in the linked list, then the current pointer would be pointing to the node containing the key to be deleted. The previous should be pointing to the node before the key node.
This can be done in a linear scan and we can simply update current and previous pointers as we iterate through the linked list.
Practice problems like this and many more by checking out our Grokking the Coding Interview: Patterns for Coding Questions course!