Delete Node In A Linked List

Easy

0/40

Average time to solve is 15m

Contributed by

155 upvotes

Asked in companies

Problem statement

You are given a Singly Linked List of integers and a reference to the node to be deleted. Every node of the Linked List has a unique value written on it. Your task is to delete that node from the linked list.

A singly linked list is a linear data structure in which we can traverse only in one direction i.e. from Head to Tail. It consists of several nodes where each node contains some data and a reference to the next node.

Note:

• The reference to the head of the linked list is not given.
• The node to be deleted is not a tail node.
• The value of each node in the Linked List is unique.
• It is guaranteed that the node to be deleted is present in the linked list.

A sample Linked List-

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

Input format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow.

The first line of each test case contains space-separated integers denoting the values of nodes of the Linked List. The Linked List is terminated with -1. Hence, -1 is never a node value of the Linked List.

The second line of each test case contains a single integer K which denotes the node to be deleted from the Linked List.

For more clarity please refer to the sample inputs.

Output format:

For each test case, delete the given node and then print a single line containing the elements of the Linked List separated by a single space, '-1' at the end denotes the end of the linked list.

The output for each test case will be printed in a new line.

Note:

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

Constraints:

1 <= T <= 100
2 <= N <= 5000
-10 ^ 9 <= NODE.DATA <= 10 ^ 9 and node.data != -1

Where 'N' denotes the total number of nodes in the Linked List and 'NODE.DATA' is the value of the node present.

Time limit: 1 sec.

Sample Input 1:

2
2 5 7 10 -1
7
-8 3 4 -2 1 -1
4

Sample Output 1:

2 5 10 -1
-8 3 -2 1 -1

Explanation for sample input 1:

For the first test case, the given Linked List is

So, after deleting the node 7, the Linked List becomes 2 → 5 → 10 → NULL, which is shown in the below figure.

For the second test case, the given Linked List is

So, after deleting the node 4, the Linked List becomes  -8 → 3 → -2 → 1 → NULL.

Sample Input 2:

Sample Output 2:

9 10 -1
7 -1

Explanation for sample input 2:

For the first test case, the given Linked List is

So, after deleting the node 4, the Linked List becomes 9 → 10 → NULL.


For the second test case, the given Linked List is

So, after deleting the node -7, the Linked List becomes 7 → NULL.

Console