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
Node: 4
Output-1
1->2->3->5
Explanation
Here, 4 is the reference node of the linked list which is given as shown below.
Input-2
Node: 9
Output-2
7->2->5->4
Explanation
Here, 9 is the reference node as well as the head of the linked list to be deleted as shown below.
Constraints
The number of nodes in the linked list is in the range [1 to 100].
1 <= Node.val <= 1000
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++
// delete without head pointer
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
void deleteNodeWithoutHead(struct Node* pos)
{
if (pos == NULL) // If linked list is empty
return;
else {
if (pos->next == NULL) {
printf("This is last node, require head, can't "
"be freed\n");
return;
}
struct Node* temp = pos->next;
// Copy data of the next node to current node
pos->data = pos->next->data;
pos->next = pos->next->next;
free(temp);
}
}
void printLinkedList(Node* head) {
Node* temp = head;
while (temp) {
cout << temp->data << " -> ";
temp = temp->next;
}
}
void insertNode(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node = new Node();
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
int main() {
struct Node* head = NULL;
insertNode(&head, 5);
insertNode(&head, 4);
insertNode(&head, 3);
insertNode(&head, 2);
insertNode(&head, 1);
cout << "Linked List before deletion:" << endl;
printLinkedList(head);
Node* del = head->next->next->next;
deleteNodeWithoutHead(del);
cout << "\nFinal Linked List after deletion of 4:"<< endl;
printLinkedList(head);
return 0;
}
Code in Java
// delete without head pointer
import java.util.*;
class node{
int data;
node next;
}
class Main{
static node create(int data){
node tmp = new node();
tmp.data = data;
tmp.next = null;
return tmp;
}
static node deletedNode(node head, node toBeDeleted){
if(toBeDeleted == null) // If linked list is empty
return null;
else{
if(toBeDeleted.next == null){
System.out.print("Last node can't be freed");
return null;
}
// Copy data of the next node to current node
toBeDeleted.data = toBeDeleted.next.data;
toBeDeleted.next = toBeDeleted.next.next;
return head;
}
}
public static void main(String[] args){
// create a linked list
node head = new node();
head = create(1);
head.next = create(2);
head.next.next = create(3);
node toBeDeleted = create(4);
head.next.next.next = toBeDeleted;
head.next.next.next.next = create(5);
System.out.print("Linked List before deletion:\n");
node tmp = head;
// print the nodes
while(tmp != null){
System.out.print(tmp.data+"->");
tmp = tmp.next;
}
head = deletedNode(head, toBeDeleted);
System.out.print("\nFinal Linked List after deletion of 4:\n");
tmp = head;
// print the nodes
while(tmp!=null){
System.out.print(tmp.data+"->");
tmp = tmp.next;
}
}
}
Code in Python
# delete without head pointer
class LinkNode :
def __init__(self, data) :
self.data = data
self.next = None
class SingleLL :
def __init__(self) :
self.head = None
# Add new node at the end of linked list
def addNode(self, value) :
# Create node
node = LinkNode(value)
if (self.head == None) :
self.head = node
else :
temp = self.head
# Find the last node
while (temp.next != None) :
# Visit to next node
temp = temp.next
# Add node at last position
temp.next = node
# Delete a node in linked list
def deleteNode(self, node) :
if (node == None) :
return
if (node.next == None) :
print("\n Not delete last node")
else :
# Change data value to next node
node.data = node.next.data
# Change link
node.next = node.next.next
# Display all Linked List elements
def display(self) :
if (self.head != None) :
temp = self.head
while (temp != None) :
# Display node value
print(" ", temp.data, end = "->")
temp = temp.next
else :
print("Linked list is empty")
def main() :
sll = SingleLL()
# Linked list
# 1 → 2 → 3 → 4 → 5 → 6 → 7 → NULL
sll.addNode(1)
sll.addNode(2)
sll.addNode(3)
sll.addNode(4)
sll.addNode(5)
print("Linked List before deletion:")
sll.display()
# Delete node 3
sll.deleteNode(sll.head.next.next.next)
print("\n Final Linked List after deletion of 4:")
sll.display()
if __name__ == "__main__": main()
Output
Linked List before deletion:
1-> 2-> 3-> 4-> 5->
Final Linked List after deletion of 4:
1-> 2-> 3-> 5->
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
