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:
Linked list: [1,4,2,3]
Node = 2
Output:
Linked list: [1,4,3]
Explanation: Access is given to node 2. After deleting nodes, the linked list will be modified to [1,4,3].
Example 2:
Input:
Linked list: [1,2,3,4]
Node = 1
Output: Linked list: [2,3,4]
Explanation:
Access is given to node 1. After deleting nodes, the linked list will be modified to [2,3,4].
Solution:
Disclaimer: Don’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
void insertNode(node* &head,int val) {
node* newNode = new node(val);
if(head == NULL) {
head = newNode;
return;
}
node* temp = head;
while(temp->next != NULL) temp = temp->next;
temp->next = newNode;
}
//function to get reference of the node to delete
node* getNode(node* head,int val) {
while(head->num != val) head = head->next;
return head;
}
//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
void printList(node* head) {
while(head->next != NULL) {
cout<<head->num<<"->";
head = head->next;
}
cout<<head->num<<"\n";
}
int main() {
node* head = NULL;
//inserting node
insertNode(head,1);
insertNode(head,4);
insertNode(head,2);
insertNode(head,3);
//printing given list
cout<<"Given Linked List:\n";
printList(head);
node* t = getNode(head,2);
//delete node
deleteNode(t);
//list after deletion operation
cout<<"Linked List after deletion:\n";
printList(head);
return 0;
}
Output:
Given Linked List:
1->4->2->3
Linked List after deletion:
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);
if(head == null) {
head = newNode;
return head;
}
Node temp = head;
while(temp.next != null) temp = temp.next;
temp.next = newNode;
return head;
}
//function to get reference of the node to delete
static Node getNode(Node head,int val) {
if(head==null)
return null;
while(head.num != val) head = head.next;
return head;
}
//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
static void printList(Node head) {
if(head==null)
return;
while(head.next!=null ) {
System.out.print(head.num+"->");
head = head.next;
}
System.out.println(head.num);
}
public static void main(String args[]) {
Node head = null;
//inserting node
head=insertNode(head,1);
head=insertNode(head,4);
head=insertNode(head,2);
head=insertNode(head,3);
//printing given list
System.out.println("Given Linked List: ");
printList(head);
Node t = getNode(head,2);
//delete node
deleteNode(t);
//list after deletion operation
System.out.println("Linked List after deletion: ");
printList(head);
}
}
Output:
Given Linked List:
1->4->2->3
Linked List after deletion:
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)
if head == None:
head = newNode
return head
temp = head
while temp.next != None:
temp = temp.next
temp.next = newNode
return head
# function to get reference of the node to delete
def getNode(head: Node, val: int) -> Node:
while head.num != val:
head = head.next
return head
# 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
def printList(head: Node) -> None:
while head.next != None:
print(head.num, end="->")
head = head.next
print(head.num)
if __name__ == "__main__":
head = None
# inserting node
head = insertNode(head, 1)
head = insertNode(head, 4)
head = insertNode(head, 2)
head = insertNode(head, 3)
# printing given list
print("Given Linked List:")
printList(head)
t = getNode(head, 2)
# delete node
deleteNode(t)
# list after deletion operation
print("Linked List after deletion:")
printList(head)Output:
Given Linked List:
1->4->2->3
Linked List after deletion:
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.
Special thanks to Dewanshi Paul and Sudip Ghosh for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article