Delete all occurrences of a given key in a doubly linked list

Moderate

0/80

Average time to solve is 30m

Contributed by

97 upvotes

Asked in company

Problem statement

A doubly-linked list is a data structure that consists of sequentially linked nodes, and the nodes have reference to both the previous and the next nodes in the sequence of nodes.

You’re given a doubly-linked list and a key 'k'.

Delete all the nodes having data equal to ‘k’.

Example:

Input: Linked List: 10 <-> 4 <-> 10 <-> 3 <-> 5 <-> 20 <-> 10 and ‘k’ = 10

Output: Modified Linked List: 4 <-> 3 <-> 5 <-> 20

Explanation: All the nodes having ‘data’ = 10 are removed from the linked list.

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

Input Format:

The first line contains an integer ‘n’, the number of nodes in the linked list.
The next line contains ‘n’ numbers, the linked list.
The third line contains an integer ‘k’, the key whose occurrences are to be removed.

Output format:

Print the modified linked list.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Sample Input 1:

7
10 4 10 3 5 20 10
10

Sample Output 1:

4 3 5 20

Explanation Of Sample Input 1:

All the nodes having ‘data’ = 10 are removed from the linked list.

Sample Input 2:

7
10 4 10 3 5 20 10
30

Sample Output 2:

10 4 10 3 5 20 10

Explanation Of Sample Input 2:

The linked list does not have any node with ‘data’ = 30. So the linked list is unchanged.

Expected Time Complexity:

The expected time complexity is O(‘n’).

Constraints:

0 <= ‘n’ <= 100000
1 <= ‘data’ in any node <= 10^9
1 <= ‘k’ <= 10^9

Console