# 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) {
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) {
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):
if temp is not None:
if temp.data == key:
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.

## 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.  