Delete Node with a Given Key

editor-page-cover

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.

widget

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

Runtime Complexity

Linear, O(n)

Memory Complexity

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.

Learn in-demand tech skills in half the time

Copyright ©2022 Educative, Inc. All rights reserved.

soc2