# Delete given node in a Linked List : O(1) approach

Problem Statement: Write a function to delete a node in a singly-linked list. You will not be given access to the head of the list instead, you will be given access to the node to be deleted directly. It is guaranteed that the node to be deleted is not a tail node in the list.

Examples:

Example 1:
Input:
Node = 2
Output:
Explanation: Access is given to node 2. After deleting nodes, the linked list will be modified to [1,4,3].

Example 2:
Input:
Node = 1
Explanation:
Access is given to node 1. After deleting nodes, the linked list will be modified to [2,3,4].

Solution:

DisclaimerDon’t jump directly to the solution, try it out yourself first.

Approach:

We are given access to nodes that we have to delete from the linked list. So, whatever operation we want to do in the linked list, we can operate in the right part of the linked list from the node to be deleted.

The approach is to copy the next node’s value in the deleted node. Then, link node to next of next node. This does not delete that node but indirectly it removes that node from the linked list.

Dry Run:

Code:

## C++ Code

#include<iostream>
using namespace std;

class node {
public:
int num;
node* next;
node(int a) {
num = a;
next = NULL;
}
};
//function to insert node at the end of the list
node* newNode = new node(val);
return;
}
while(temp->next != NULL) temp = temp->next;
temp->next = newNode;
}
//function to get reference of the node to delete

}
//delete function as per the question
void deleteNode(node* t) {
t->num = t->next->num;
t->next = t->next->next;
return;
}
//printing the list function
}
}

int main() {
//inserting node
//printing given list
//delete node
deleteNode(t);
//list after deletion operation
return 0;
}

Output:

1->4->2->3
1->4->3

Time Complexity: O(1)

Reason: It is a two-step process that can be obtained in constant time.

Space Complexity: O(1)

Reason: No extra data structure is used.

## Java Code

import java.util.*;
class Node {
int num;
Node next;
Node(int a) {
num = a;
next = null;
}
}
class TUF{
//function to insert node at the end of the list
static Node insertNode(Node head,int val) {
Node newNode = new Node(val);
}
while(temp.next != null) temp = temp.next;
temp.next = newNode;
}
//function to get reference of the node to delete
static Node getNode(Node head,int val) {
return null;

}
//delete function as per the question
static void deleteNode(Node t) {
if(t==null)
return;
t.num = t.next.num;
t.next = t.next.next;
return;
}
//printing the list function
return;
}
}

public static void main(String args[]) {
//inserting node
//printing given list
//delete node
deleteNode(t);
//list after deletion operation
}
}

Output:

1->4->2->3
1->4->3

Time Complexity: O(1)

Reason: It is a two-step process that can be obtained in constant time.

Space Complexity: O(1)

Reason: No extra data structure is used.

## Python Code

class Node:
def __init__(self, num: int):
self.num = num
self.next = None

# function to insert node at the end of the list
def insertNode(head: Node, val: int) -> Node:
newNode = Node(val)
while temp.next != None:
temp = temp.next
temp.next = newNode

# function to get reference of the node to delete

def getNode(head: Node, val: int) -> Node:

# delete function as per the question
def deleteNode(t: Node) -> None:
t.num = t.next.num
t.next = t.next.next
return

# printing the list function

if __name__ == "__main__":
# inserting node
# printing given list
# delete node
deleteNode(t)
# list after deletion operation

Output: