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

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.  