# Delete Node with a Given Key

## Problem Statement

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.

## Hint

• Keep track of previous pointer

## Try it yourself

LinkedListNode* delete_node(    LinkedListNode* head,    int key) { //TODO: Write - Your - Code  return head;}

## Solution

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 list  if (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);}

## Solution Explanation

Linear, O(n)

Constant, O(1)

### Solution Breakdown

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!

Learn in-demand tech skills in half the time