  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

Last Updated on March 10, 2022 by Ria Pathak ### 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

In this question, we are given a singly linked list and a value X. We have to delete the first occurrence of a node with the data X from the linked list.

Note: Although there can be multiples nodes with value X in the linked list, but we have to only delete the first node with value X from the linked list.

### Problem Statement Understanding

Let’s try to understand the problem statement with the help of examples.

Suppose the given linked list is: 1 → 1 → 0 → 2 → 2 and the value to be deleted is 0.

• Now, according to the problem statement, we have to delete the first occurrence of the node containing the value 0.
• So, the linked list after deleting 0 will be 1 → 1 → 2 → 2.

Suppose the list is:. and the value to be deleted is 2

• Now, in this case, we can see that there are two nodes with data 2 in the linked list. According to the problem statement, we only need to delete the first occurrence of the node with value 2 from the linked list.
• Our output linked list after deletion will be ##### Some more examples

Sample Input 1: 1 → 2 → 3 →4, Value to be deleted (X) = 2
Sample Output 1: 1 → 3 → 4

Sample Input 2: 1 → 1 → 2 →2, Value to be deleted (X) = 1
Sample Output 2: 1 → 2 → 2

Now, I think from the above examples, the problem statement is clear. Let’s see how we can approach it.

Before moving to the approach section, try to think about how can you 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.

### Approach (Iterative)

Let us first think about what we should do to delete a node from a linked list.

Let us take an example. 1 → 2 → 3 → 4. Now, to delete 2 from the list, what should we do?

• What if we make 1 point to 3 instead of 2 ? Yes. That’s the essence.

To delete a node P from a linked list, we have to traverse to its previous node and make it point to the P‘s next node.

Let’s see the algorithm.

### Algorithm

• Create a pointer temp and make it point to the head of the list and also create a pointer prev and point it to NULL.
• If the head contains the value X, make head = temp → next, and then delete temp.
• Else, we will traverse the list with temp and store temp in pointer prev before incrementing it.
• The loop will run till temp → data! = X.
• As soon as temp → data = X, the loop will break.
• As we were storing temp in prev before incrementing it, so prev now points to the previous node of the node which we want to delete.
• Now, we will simply do prev -> next = temp -> next, as discussed in the approach.
• Finally, delete temp.
• In this way, the first occurrence of a node with value X will be deleted. If the list is traversed and the value is not found, we will simply return.

### Dry Run ### Code Implementation

```#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
};

/* Given a reference (pointer to pointer) to the head of a
list and an int, inserts a new node on the front of the
list. */
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node
= (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
}

/* Given a reference (pointer to pointer) to the head of a
list and a key, deletes the first occurrence of key in
void deleteNode(struct Node** head_ref, int key)
{
struct Node *temp = *head_ref, *prev;

// If head node itself holds the key to be deleted
if (temp != NULL && temp->data == key) {
return;
}

// Search for the key to be deleted, keep track of the
// previous node as we need to change 'prev->next'
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}

// If key was not present in linked list
if (temp == NULL)
return;

prev->next = temp->next;

free(temp); // Free memory
}

// This function prints contents of linked list starting
// from the given node
void printList(struct Node* node)
{
while (node != NULL) {
printf(" %d ", node->data);
node = node->next;
}
}

// Driver code
int main()
{

puts("\nLinked List after Deletion of 1: ");
return 0;
}
```
```#include <bits/stdc++.h>
using namespace std;

/* Node structure of linked list node */
class Node{
public:
int data;
Node* next;
};

/* Using this function we will insert a new node at head of linked list */
{
Node* new_node = new Node();
new_node->data = new_data;
}

/* Using this function we will be deleting the first occurance of a node with value = key from the linked list */
{

Node* prev = NULL;

if (temp != NULL && temp->data == key)
{
delete temp;
return;
}

else
{
while (temp != NULL && temp->data != key)
{
prev = temp;
temp = temp->next;
}

if (temp == NULL)
return;

prev->next = temp->next;

delete temp;
}
}

/* Using this function we will be printing the content of linked list */
void print(Node* node)
{
while (node != NULL)
{
cout << node->data << " ";
node = node->next;
}
}

int main()
{

int X = 2;
cout<<"\nLinked List after Deletion of first occurance of node with value "<<X<<": "<<endl;

return 0;
}
```
```public class LinkedList {

/* Node structure of a linked list node */
class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}

/* Using this function we will be deleting the first occurance of a node with value = key from the linked list */
void deleteValue(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;
}

/* Using this function we will insert a new node at head of linked list */
public void push(int new_data)
{
Node new_node = new Node(new_data);
}

/* Using this function we will be printing the content of linked list */
public void printList()
{
while (tnode != null) {
System.out.print(tnode.data + " ");
tnode = tnode.next;
}
}

public static void main(String[] args)
{

llist.push(4);
llist.push(3);
llist.push(2);
llist.push(1);

llist.printList();

int X = 2;
llist.deleteValue(X);

System.out.println(
"\nLinked List after Deletion of first occurance of node with value "+X+": ");
llist.printList();
}
}
```
```class Node:

def __init__(self, data):
self.data = data
self.next = None

def __init__(self):

def push(self, new_data):
new_node = Node(new_data)

def deleteNode(self, 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

def printList(self):
while(temp):
print (temp.data, end = " ")
temp = temp.next

llist.push(4)
llist.push(3)
llist.push(2)
llist.push(1)

llist.printList()
llist.deleteNode(2)
print ("\nLinked List after Deletion of 2:")
llist.printList()

```

#### Output

1 2 3 4
Linked List after Deletion of first occurance of node with value 2:
1 3 4

Time Complexity: O(n), as list traversal is needed.
Space Complexity: O(1), as only temporary variables are being created.

### Approach (Recursive)

As we have already discussed what we have to do to delete a node from a linked list, now here we will modify it a lit bit while implementing.

• 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 altering the current node can alter the previous node’s next.
• So, we will traverse the linked list with the help of recursion, and when the head’s data is equal to the value of node to be deleted(X), we will store the head in temp, do head = head → next and delete temp and then return 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.

Let’s see the algorithm.

### Algorithm

• Base case – If the head is NULL, i.e., the node with value X is not present in the list, so we will print Element not present in the list and then we will return.
• If the head → data = X, then store the head in a pointer temp, do head = head → next and delete temp and then return as our task is completed. This will change the required links too as discussed above.
• Keep recurring with deleteValue( head – > next, X).

### Dry Run ### Code Implementation

```#include
#include

struct Node {
int data;
struct Node* next;
};

/* Recursive Function to delete the entire linked list */
{
return;
}

/* Given a reference (pointer to pointer) to
the head of a list and an int, push a new
node on the front of the list. */
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node = new Node;
new_node->data = new_data;
}

/* Driver program to test count function*/
int main()
{

/* Use push() to construct below list
1->12->1->4->1 */

return 0;
}
```
```#include
using namespace std;

struct node {
int info;
node() {}
node(int a)
: info(a)
{
}
};

/* Using this function we will be deleting the first occurance of the given valued node from the linked list */
{

cout << "Element not present in the list\n";
return;
}

delete (temp);
return;
}
}

/* Using this function we will push the node in the list */
{
node* newNode = new node(data);
}

/* Using this function we will print the content of linked list */
{

if (head == NULL and cout << endl)
return;
cout << head->info << ' ';
}

int main()
{

int X = 2;

cout<<"\nLinked List after Deletion of first occurance of node with value "<

```
```class Node
{
int info;
Node(int info)
{
this.info=info;
}
}

class DeletingNode
{
{
Node newNode = new Node(data);
}
{
while(temp!=null){
System.out.print(temp.info+" ");
}
}

{
{
System.out.println("Element not present in the list");
return;
}
{
return;
}
}
public static void main(String[] args)
{
DeletingNode ll=new DeletingNode();

int x=2;

System.out.println("Linked list after deletion of first occurance of node with value "+x);
ll.print(temp);
}
}
```
```class Node:

def __init__(self, data):
self.data = data
self.next = None

def __init__(self):

def push(self, new_data):
new_node = Node(new_data)

def printList(self):
while(temp):
print (temp.data, end = " ")
temp = temp.next

print("Element not present in the list")
return

del temp
return

llist.push(4)
llist.push(3)
llist.push(2)
llist.push(1)

llist.printList()
print ("\nLinked List after Deletion of 2:")
llist.printList()

```