Delete Node In A Linked List

Easy
0/40
Average time to solve is 15m
profile
Contributed by
169 upvotes
Asked in companies
HSBCAdobeCIS - Cyber Infrastructure

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-

singly_linkedlist

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

explanation

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

explanation

For the second test case, the given Linked List is

explanation

So, after deleting the node 4, the Linked List becomes  -8 → 3 → -2 → 1 → NULL.
Sample Input 2:
2
4 9 10 -1
4
-7 7 -1
-7
Sample Output 2:
9 10 -1
7 -1
Explanation for sample input 2:
For the first test case, the given Linked List is

explanation

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


For the second test case, the given Linked List is

explanation

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

Think of a solution to store the data of the next node in the node that is to be deleted.

Approaches (1)
Brute-force

Approach:

 

We need to delete the node K from the linked list. The most general way to delete the node K from a singly linked list is to get access to the previous node of K. We can get access to the previous node by traversing from the head of the linked list. Let’s denote this previous node as P. Then, we update the next pointer of P to the next pointer of K. 

Although the reference to node K is given, we do not have access to the head of the linked list. So, there is no way in which we can reach the previous node of K. Thus we have to store the data of the next node of K in the node K itself and then delete the next node of K by making K.next = K.next.next 

 

Steps:

 

  1. Create a temp pointer that points to the next node of the node K i.e. temp = K.next
  2. Store the data of temp in the node K and make K.next = temp.next.
  3. Finally, delete/free the temp node. Note, that in languages like C/C++, we do this step to avoid memory leak.
Time Complexity

O(1).

 

As all operations are performed in constant time.

Space Complexity

O(1).

 

As we are using constant extra memory

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Delete Node In A Linked List
Full screen
Console