### Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

### Problem Statement

Delete a node with a given key from the given linked list and in case there are multiple occurrences of a given key in the linked list, then delete the first occurrence of this key in the linked list.

### Problem Statement Understanding

According to the problem statement, we are given a linked list and we have to delete a node with a given key value, it may be present anywhere in the linked list but, there can be two different situations are first being when there is more than one node having the same key and the next being when the node is not at all present in the linked list, so now, you all might think that what we need to do?

In the case where there are multiple nodes, you will just have to delete the first node in the linked list with the value equal to the key, and in the case where the node to be deleted is not present at all in the linked list then simply return and exit the program.

Now, let us understand this problem by taking a very simple example:

If the given linked list is:

**key** = 7

- According to the problem statement, we have been provided a linked list and a
**key**, and we need to delete the**key**from the given linked list. - As we can see in the above example, 7 is present in the linked list which needs to be deleted.
- So after deleting the key from the linked list, the resultant linked list will be:

Let’s see another example:

If the given linked list is: 1 β 2 β 3 β 4 β 5 and **key** = 4

- According to the problem statement, we have been provided a linked list and a
**key**, and we need to delete the**key**from the given linked list. - As we can see in the above example, 4 is present in the linked list which needs to be deleted.
- So after deleting the key from the linked list, the resultant linked list will be 1 β 2 β 3 β 5.

Now I think from the above examples, the problem is clear. So letβs see how we can approach it.

Before moving to the approach section, try to think about how you can approach this problem.

- If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.

Letβs move to the approach section. Now, first, letβs discuss the recursive approach to this problem and understand how it works, we will simply follow the steps to understand initially how recursion works for deleting a node from the linked list.

### Approach: (Recursive)

- Now, if we think carefully, the current node is accessed by the previous nodeβs next, which is passed by reference. Thus, we can say that if we update the current node, previous nodeβs next will also get updated.
- So, we will traverse the linked list with the help of recursion, and when the data of head is equal to the value to be deleted, we will store the head in del_node, do head = head β next and then delete del_node and then return and terminate the function as our task is completed.
- By doing the above steps, the node will get deleted and as discussed above, when we will do head = head β next, it will make the previous β next point to head β next.

I hope the above approach might have just given you the basic idea of how recursion will work here, so now letβs look at the algorithm for this method

### Algorithm: (Recursive)

Now, letβs completely understand the algorithm behind the recursive method, and we will simply follow the steps to delete the node with the given key.

- Create a function
**deleteNodeWithKey**to delete the node with the given key and pass head by reference to the function and the key. - Check if head is NULL, that means the list is empty or the node to be deleted is not in the list. Simply, return.
- Else, check if *
*((*head)->val == key)**, that means current node is the node to be deleted. Now, create a temporary variable**del_node**to store the node to be deleted. Now free**del_node**variable and update*head = (*head)->next; so that previous node’s next become head->next and return.

As we know that the current node is accessed by the previous nodeβs next, which is passed by reference. hus, we can say that if we update the current node, previous nodeβs next will also get updated.- Else, Recursively call the function deleteNodeWithKey and pass the reference to the next node in the linked list *
*deleteNodeWithKey(&((*head)->next), key);**.

- Else, Recursively call the function deleteNodeWithKey and pass the reference to the next node in the linked list *

- Else, check if *

### Dry run

### Code

#include#include // A linked list node struct Node { int val; struct Node* next; }; // Function to insert the node void pushNode(struct Node** head_ref, int data) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->val = data; new_node->next = (*head_ref); (*head_ref) = new_node; } // Function to delete the node with the given key void deleteNodeWithKey(struct Node** head, int key) { // If head is NULL, then the list is empty if (head == NULL) { return; } // If current node is the node to be deleted if ((*head)->val == key) { struct Node* del_node = (*head); *head = (*head)->next; free(del_node); return; } deleteNodeWithKey(&((*head)->next), key); // Recursively call the function passing the reference and key to the node } // Print the linked list void printList(struct Node* node) { while (node != NULL) { printf(" %d ", node->val); node = node->next; } } //Print the linked list after deletion void printListPostDeletion(struct Node* node) { while (node != NULL) { if(node->val != 0) printf(" %d ", node->val); node = node->next; } } // Driver code int main() { /* Start with the empty list */ struct Node* head = NULL; pushNode(&head, 1); pushNode(&head, 5); pushNode(&head, 7); pushNode(&head, 15); pushNode(&head, 20); printf("Linked list before deleting the key\n"); printList(head); printf("\n"); deleteNodeWithKey(&head, 7); printf("Linked list after deleting the key\n"); printListPostDeletion(head); return 0; }

**Output**

Linked list before deleting the key

20 β 15 β 7 β 5 β 1

Linked list after deleting the key

20 β 15 β 5 β 1

**Time Complexity**: The time complexity of this algorithm will be O(n), where n is the number of nodes in the given linked list

**Space Complexity**: The space complexity of the above algorithm will be O(n) due to recursion.

Now, let’s see iterative approach.

### Approach (Iterative Method)

Now, let us discuss the most common and easiest approach to delete a node from the linked list.

- Iterate to the node which is present just before the node to be deleted.
- Now, set the next of the current node to the next of the node to be deleted.
- Then, free the memory of the node to be deleted.

Now, you all might be a bit clear from the approach on what we need to do exactly right?

Now, to get a bit more clear understanding of the implementation let us have a look at the algorithm which explains the full operation step by step

### Algorithm (Iterative Method)

Now, letβs understand the algorithm on how to implement and think upon the code which we have to write for solving the given problem:

- Declare a pointer
**node_itr**which will initially point to**head**and will be used to iterate through the linked list which will help us to find the node to be deleted and another pointer**prev_node**which will initially point to NULL and point to the previous node of the node which has to be deleted. - Now, check if
**node_itr**is not NULL and**node_itr->data==key**that means the key to be deleted is the head node, then we will change the reference to the head node to the next node of**node_itr**and delete**node_itr**and return. - Else, move
**node_itr**forward and also keep track of previous node**node_prev = node_itr**and search for the node with the given key to be deleted in the linked list. - Now, if
**node_itr**becomes NULL that means the node is not present in the given linked list then simply return and end the process. - Else, point the next of the
**prev_node**to next of**node_itr**, the node which has to be deleted, and finally delete the node.

### Dry Run:

### Code Implementation

#include#include struct Node { int data; struct Node* next; }; void pushNode(struct Node** head_ref, int data) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = data; new_node->next = (*head_ref); (*head_ref) = new_node; } // Function to delete the node with given key void deleteGivenNode(struct Node** head_ref, int key) { struct Node *node_itr = *head_ref, *prev_node; if (node_itr != NULL && node_itr->data == key) { *head_ref = node_itr->next; free(node_itr); return; } while (node_itr != NULL && node_itr->data != key) { prev_node= node_itr; node_itr= node_itr->next; } if (node_itr == NULL) return; prev_node->next = node_itr->next; free(node_itr); } //Function to print the linked list void printList(struct Node* node) { while (node != NULL) { printf(" %d ", node->data); node = node->next; } } int main() { struct Node* head = NULL; pushNode(&head, 1); pushNode(&head, 5); pushNode(&head, 7); pushNode(&head, 15); pushNode(&head, 20); printf("Linked list before deleting the key\n"); printList(head); printf("\n"); printf("Linked list after deleting the key\n"); deleteGivenNode(&head, 1); printList(head); return 0; }

**Output**

Linked list before deleting the key

20 β 15 β 7 β 5 β 1

Linked list after deleting the key

20 β 15 β 7 β 5

**Time Complexity**: The time complexity of this algorithm will be O(n), where n is the number of nodes in the given linked list

**Space Complexity**: The space complexity of the above algorithm will be O(1) as we are not using any additional data structure to manipulate the nodes

So, in this article, we have tried to explain the most efficient approach to flatten a binary tree to a linked list. This is an important question when it comes to coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.