Difficulty Level Easy
Frequently asked in GE Healthcare MAQ

## Problem Statement

The problem “Delete a Node from linked list without head pointer” states that you have a linked list with some nodes. Now you want to delete a node but you don’t have its parent node address. So delete this node.

## Example ```2->3->4->5->6->7
Node to be deleted: 4```
`2->3->5->6->7`

Explanation: Since we wanted to delete the node with value 4. We removed it from the linked list and are left with a list that is mentioned in the output.

## Approach to delete node without head pointer

### If head pointer was given

Now the problem asks us to delete a node. Generally, we are given a node’s address and are required to delete the next node in the linked list. But here we are required to delete a node whose address is given to us. One way to solve this problem is to first traverse the whole linked list. Then store the parent of each node and break the loop when you are at a node that is provided as input. This way in the end we have the parent of the node to be deleted. So now the problem is changed to the simple deletion of a node in the linked list whose parent’s address is given. But doing this will cost us O(N) operations. But this way can be used only when you have the head pointer.

### Solution

The approach for the problem “Delete a Node from linked list without head pointer” would be to swap the data of the node to be deleted and the next node in the linked list. Each node in the linked list stores which node is next. So this operation has only O(1) time complexity. Now when the data has been swapped. Once again, we have changed the problem to the deletion of the node whose parent’s address is given. So now it’s easier for us to solve the problem. But there is one edge case when we have to delete the end node but we won’t be able to delete that. Because there is no next node.

## Code

### C++ code to delete a node without head pointer

```#include <bits/stdc++.h>
using namespace std;

struct node{
int data;
node* next;
};

node* create(int data){
node* tmp = new node();
tmp->data = data;
tmp->next = NULL;
return tmp;
}

if(toBeDeleted == NULL)
return;
else{
if(toBeDeleted->next == NULL){
cout<<"Last node can't be freed";
}
// store or swap but ( the data of current node will be deleted)
toBeDeleted->data = toBeDeleted->next->data;
toBeDeleted->next = toBeDeleted->next->next;
}
}

int main(){
node* toBeDeleted = create(4);

while(tmp!=NULL){
cout<<tmp->data<<" ";
tmp = tmp->next;
}

while(tmp!=NULL){
cout<<tmp->data<<" ";
tmp = tmp->next;
}
}
```
```Old Linked List: 2 3 4 5 6 7
New Linked List: 2 3 5 6 7```

### Java code to delete a node 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)
return null;
else{
if(toBeDeleted.next == null){
System.out.print("Last node can't be freed");
return null;
}
// store or swap but ( the data of current node will be deleted)
toBeDeleted.data = toBeDeleted.next.data;
toBeDeleted.next = toBeDeleted.next.next;
}
}

public static void main(String[] args){
node toBeDeleted = create(4);

while(tmp != null){
System.out.print(tmp.data+" ");
tmp = tmp.next;
}

while(tmp!=null){
System.out.print(tmp.data+" ");
tmp = tmp.next;
}
}
}```
```Old Linked List: 2 3 4 5 6 7
New Linked List: 2 3 5 6 7```

## Complexity Analysis

### Time Complexity

O(1), because swapping can be down in constant time. And then we just change some pointers which is again a constant time operation.

### Space Complexity

O(1), because the variables which we have used do not depend on the number of nodes in the linked list. Thus space complexity is also constant.

Translate »