## 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