Delete a Given Node

Easy

0/40

Average time to solve is 15m

10 upvotes

Asked in companies

Problem statement

Ninja is learning data structures and came across a doubly linked list. Now he wants to remove a particular element from the linked list. Can you help Ninja do so and return the final linked list?

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains a single integer T, denoting the number of test cases. 

The first line of each test case contains a Linked list of length N separated by space and terminated by -1.

The second and last line contains an element that has to be removed from the linked list.

Output Format

The first and only line of each test case in the output contains the linked list after deleting the required element.

Note:

You are not required to print the expected output; it has already been taken care of. Just implement the function. If there are multiple nodes with the given value remove just the first one.

Constraints:

1 <= T <= 5
1 <= N <= 10^5
-10^5 <= arr[i] <= 10^5

Time Limit: 1 sec

Sample Input 1:

2
1 2 3 4 5 6 -1
3
1 2 3 4 5 -1
4

Sample Output 1:

1 2 4 5 6 -1
1 2 3 5 -1

Explanation for Sample Output 1:

In the first test case, the given linked list is (1, 2, 3, 4, 5, 6), and the element to be removed is          3, so after removing it, the final linked list is (1, 2, 4, 5, 6) and we return it. We omit -1 because it signifies the end of the linked list.

In the second test case, the given linked list is (1, 2, 3, 4, 5,) and the element to be removed is          4, so after removing it, the final linked list is (1, 2, 3, 5) and we return it. We omit -1 because it signifies the end of the linked list.

Sample Input 2:

Sample Output 2 :

4 -1
1 2 -1

Hint 1

Can you find the element to be removed?

Approaches (1)

Approach 1

Brute Force

We will traverse the linked list from the head node till we find the node that has to be removed, and upon getting that, we remove it and return the linked list.

The steps are as follows:

If the head is NULL, then we don't have to delete anything, return NULL in this case.
We declare a node ‘h’ pointing to the head.
If the head is equal to the node we have to remove, then we move the head pointer to the node next to the node that needs to be removed.
While the Node ‘h’ is not NULL and the value of the Node ‘h’ node is not equal to the given node value traverse linked list.
Remove the current node ‘h’ and return' head' as the final answer.

Time Complexity

O(N), where N is the number of elements of the linked list.

As we are traversing all the nodes from1 to ‘N’, there are most ‘N’ iterations. Hence, the overall complexity is O(N).

Space Complexity

O(1), no extra space required.

As we are not using any extra space. Hence, the overall space complexity is O(1).

(100% EXP penalty)

Delete a Given Node

Console