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.
- Traverse the linked list and for the current node curr, check whether the next node contains the key that needs to be deleted.
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:
FAQs
Q.1: How to delete a node from the end of the linked list?
Ans: 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.2: What is the time complexity and space complexity of the iterative approach?
Ans: The time complexity is O(N) and the space complexity is O(1), where N is the total node of the linked list.
