# Remove Linked List Elements Leetcode Solution

Difficulty Level Easy
algorithms coding Interview interviewprep LeetCode LeetCodeSolutions Linked-List Pure StorageViews 262

## Problem Statement

In this problem, we are given a linked list with its nodes having integer values. We need to delete some nodes from the list which have value equal to val. The problem does not require to be solved in-place but we will discuss one such approach.

### Example

`List = 1 -> 2 -> 2 -> 3 -> 4 , val = 2`
`1 3 4`
`List = 2 -> 2 -> 2 -> 2 , val = 2`
`Empty List`

## Approach (Recursive)

We can recursively call the same function to return the head of the required list. We achieve this by calling the function on subsequent suffixes of the given list with some conditions. However, we need to handle the base case when the list is empty. There is only one special case:

If the head of the list has a value equal to val(input), then, we need to return the function called on its next node. This is done to avoid the current node to be appended to the previous nodes of the list (as the function stack is completed).

### Implementation of Remove Linked List Elements Leetcode Solution

#### C++ Program

```#include <bits/stdc++.h>

using namespace std;

struct listNode
{
int value;
listNode* next;
listNode(int x)
{
value = x;
next = NULL;
}
};

{
cout << "Empty List\n";
return;
}
{
cout << head->value << " ";
}
cout << '\n';
return;
}

listNode* removeElements(listNode* head, int val) {
}
return removeElements(temp , val);
}

}

int main() {

int val = 2;
return 0;
}```

#### Java Program

```class listNode
{
int value;
listNode next;
listNode(int x)
{
value = x;
next = null;
}
};

public static void print(listNode head) {
System.out.println("Empty List");
return;
}
{
}
System.out.println();
return;
}

public static listNode removeElements(listNode head, int val) {
}
}

}

public static void main(String args[]) {

int val = 2;
}
}```
`1 3 4`

### Complexity Analysis of Number Complement Leetcode Solution

#### Time Complexity

O(N), where N = length of the list. We visit each element only once in the worst case.

#### Space Complexity

O(1). As the code follows tail recursion.

## Approach (Iterative)

In order to delete any node, we need to have the address of its previous node, so that we can make the previous point to its next. This gives an idea to maintain a previous pointer that will help us to manipulate pointers in the list. Now, the important point is that the first node in the list does not have any previous node. So, we need to add a sentinel node in the beginning of the list. Now, we can traverse through the first node in the list(node next to sentinel node) and would face following two conditions:

1.) node->value == val: In this case, we will set prev->next = node->next. This will connect the previous of the current node with the next of the current node, and delete the current node using: delete(currentNode)

2.) Otherwise, we just set prev = head for upcoming nodes.

At the end, the next of sentinel is the required list.

### Implementation of Remove Linked List Elements Leetcode Solution

#### C++ Program

```#include <bits/stdc++.h>

using namespace std;

struct listNode
{
int value;
listNode* next;
listNode(int x)
{
value = x;
next = NULL;
}
};

{
cout << "Empty List\n";
return;
}
{
cout << head->value << " ";
}
cout << '\n';
return;
}

listNode* removeElements(listNode* head, int val) {
listNode *dummy = new listNode(-1) , *prev = dummy , *toDelete;

toDelete->next = NULL;
}
else {
toDelete = NULL;
}
if(toDelete != NULL)
delete(toDelete);
}

return dummy->next;
}

int main() {

int val = 2;
return 0;
}```

#### Java Program

```class listNode
{
int value;
listNode next;
listNode(int x)
{
value = x;
next = null;
}
};

public static void print(listNode head) {
System.out.println("Empty List");
return;
}
{
}
System.out.println();
return;
}

public static listNode removeElements(listNode head, int val) {
listNode dummy = new listNode(-1) , prev = dummy , toDelete;

}
else {
}
}

return dummy.next;
}

public static void main(String args[]) {

int val = 2;
}
}
```
`1 3 4`

### Complexity Analysis of Remove Linked List Elements Leetcode Solution

#### Time Complexity

O(N), as we iterate the whole list once. N = length of the list

#### Space Complexity

O(1), as we only constant memory space.

Translate »