Delete Node In A Linked List
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-

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

Question

Delete Node In A Linked List

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

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.

Accepted Answer

Step 1 : I wrote all condition for deletion in linked list first from the beginning of the linked list then between linked list and then deleting last node for linked list
Step 2 : Interviewer asked about complexity for each of them i replied for all three cases.
Step 3 : Then i explained it using diagram how we are implementing this algo
Step 4 : He found an error in my code when we have only one node
Step 5 : I resolved that one then he was satisfied

Accepted Answer

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:

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

Space Complexity: O(1)Explanation:

O(1).

As we are using constant extra memory

Time Complexity: O(1)Explanation:

O(1).

As all operations are performed in constant time.

Java (SE 1.8)

/*

    Time Complexity - O(1)

    Space Complexity - O(1)

*/



public class Solution {

	public static void deleteNode(LinkedListNode node) {

		// Create a temp pointer that initially points to node -> next.

		LinkedListNode  temp = (node == null) ? node : (node.next);



		// Store the data of temp as node -> data and make node -> next = temp -> next.

		node . data = temp . data;

		node . next = (temp == null) ? null : (temp . next);



		// Finally delete the temp pointer.

		temp = null;

	}



}

C++ (g++ 5.4)

/*
    Time Complexity - O(1)
    Space Complexity - O(1)
*/

void deleteNode(LinkedListNode * node) 
{
	// Create a temp pointer that initially points to node -> next.
    LinkedListNode * temp = node->next;

    // Store the data of temp as node -> data and make node -> next = temp -> next.
    node -> data = temp -> data;
    node -> next = temp -> next;

    // Finally delete the temp pointer.
    delete temp;
}

Python (3.5)

'''
    Time Complexity: O(1)
    Space complexity: O(1)
'''

def deleteNode(node):

	# Create a temp node that initially points to node -> next.
	temp = node.next

	# Store the data of temp as node -> data and make node -> next = temp->next.
	node.data = temp.data
	node.next = temp.next

	# Finally delete the temp node.
	del temp

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:

A sample Linked List-

Input format:

Output format:

Note:

Constraints:

Top UnitedHealth Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in UnitedHealth Software Developer