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

- If true, point

- Traverse the linked list and for the current node

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.