Delete a Node without Head Pointer

Problem Statement

You are given a singly linked list and the reference to the node to be deleted in the linked list, write a program to delete that node from linked list. There is no information provided about the head pointer or any other node.

The normal deletion would fail here as the linked list we are given is a singly linked list, therefore, we cannot go back as we don’t have knowledge of the previous node of a node to delete without head pointer.

In this question, No head reference is given. And there is no case when the node to be deleted is the last node.

:::

Example

Input-1

Output-1

Explanation

Here, 4 is the reference node of the linked list which is given as shown below.

Input-2

Output-2

Explanation

Here, 9 is the reference node as well as the head of the linked list to be deleted as shown below.

Constraints

Algorithm 1

Intuition:

The idea here is to just copy the data of the next node to update the current node’s value to be deleted with the value of its next node and finally point the next node of the current node to the next of next node. As a result, next has become the current node and the current has been deleted.

Algorithm

Check whether the pointer to the next node is null.
If so, move on to step 3, Else go to step 4.
Copy the data of the next node to update the current node’s value to be deleted.
Now, move the pointer of the current node to its next node.
At last, return the current node.

Code Implementation

Code in C++

Code in Java

Code in Python

Output

Time Complexity

The time complexity is O(1). Since we are doing constant operations and updating only one reference node to delete without head pointer in linked list.

Space Complexity

The space complexity is O(1). Since no extra space is used in the Program to delete without head pointer in linked list.

Conclusion

We have given a singly linked list and the reference to the node to be deleted in the linked list. We had to write a program to delete without head pointer from linked list.
The most important thing to keep in mind that there is no information provided about the head pointer or any other node.
For eg, A reference of the node is given 4 of linked list 1->2->3->4->5, here the output should be 1->2->3->5.
The idea is to just copy the data of the next node to modify the current node’s value and point the next node of the current node to the next of next node.
The Algorithm takes O(1) time complexity as we are doing constant operations, and O(1) space complexity because no extra space is used.
The normal deletion would fail in this approach as the linked list we are given is a singly linked list, therefore, we don’t have the knowledge of the previous node of a node.

FAQ

Q. Will the above approaches work if the node given is the last node?

A. No, In that case, the last node node -> next will be equal to NULL. Also, It is mentioned that the last node will not be given to delete without head pointer.

Q. What if we try to delete by using normal conventional deletion methods?

A. The normal deletion would fail here as the linked list we are given is a singly linked list, therefore, we cannot go back as we don’t have knowledge of the previous node of a node.

Q. Can we solve the above problem with some different approach?

A. No, However, there can be some cases when we can delete without a head pointer but sing extra memory space, by storing all nodes in some memory. But the space complexity will not be constant.

Q. What are some similar coding questions of Linked List.

A. Refer Delete Node in a Linked List
Refer Remove Nth Node from List End
Refer Reverse a Linked List