Delete Node in a Linked List

Delete Node in a Linked List

Problem Statement

Given the linked list. The task is to delete the node of the linked list and return the list.

Examples:

Input: 4 -> 5 -> 1 -> 9
Key = 5
Output: 4 -> 1 -> 9 -> NULL
Explanation:

Input: 10 -> 20 -> 30 -> NULL
Key = 20
Output: 10 -> 30 -> NULL

Approach: Iterative

The approach is based on a few observations.

Algorithm

  • If the node to be deleted is the head node, then simply point the head to the second node of the linked list.
  • For all other nodes:
    • Traverse the linked list and for the current node curr, check whether the next node contains the key that needs to be deleted.
      • If true, point curr -> next to curr -> next -> next.
      • Else, keep traversing the list until the end of the linked list.

The following illustration will make the approach more clear.

C++ Code

void deleteNode(struct node ** head, int key) {
  struct node * temp;
  if (( * head) -> data == key) {
    temp = * head;
    * head = ( * head) -> next;
    free(temp);
  } else {
    struct node * current = * head;
    while (current -> next != NULL) {
      if (current -> next -> data == key) {
        temp = current -> next;
        current -> next = current -> next -> next;
        free(temp);
        break;
      } else
        current = current -> next;
    }
  }
}

Java Code

 void deleteNode(int key) {
  Node temp = head, prev = null;
  if (temp != null && temp.data == key) {
    head = temp.next;
    return;
  }
  while (temp != null && temp.data != key) {
    prev = temp;
    temp = temp.next;
  }
  if (temp == null)
    return;
 
  prev.next = temp.next;
}

Python Code

def deleteNode(key):
    temp = head
    if temp is not None:
        if temp.data == key:
            self.head = temp.next
            temp = None
            return
 
    while temp is not None:
        if temp.data == key:
            break
        prev = temp
        temp = temp.next
 
    if temp == None:
        return
 
    prev.next = temp.next
 
    temp = None

Time Complexity: O(N), where N is the total nodes of the linked list.
Space Complexity: O(1) since no extra space is used.

Practice Question – Remove Nth Node from List End

FAQs

Q. How to delete a node from the end of the linked list?
A. If the node to be deleted is at the end of the linked list, traverse till the second last node, say curr, and mark curr -> next = NULL and free the memory.

Q. What is the time complexity and space complexity of the iterative approach?
A. The time complexity is O(N) and space complexity is O(1), where N is the total node of the linked list.

Additional Resources

Previous Post
Letter combinations of a phone number

Letter Combinations of a Phone Number

Next Post
Tree Diameter - Diameter of a Binary Tree

Tree Diameter – Diameter of a Binary Tree

Total
0
Share