Delete a given node in Linked List under given constraints
Last Updated :
10 Jan, 2023
Given a Singly Linked List, write a function to delete a given node. Your function must follow following constraints:
1) It must accept a pointer to the start node as the first parameter and node to be deleted as the second parameter i.e., a pointer to head node is not global.
2) It should not return a pointer to the head node.
3) It should not accept pointer to pointer to the head node.
You may assume that the Linked List never becomes empty.
Let the function name be deleteNode(). In a straightforward implementation, the function needs to modify the head pointer when the node to be deleted is the first node. As discussed in previous post, when a function modifies the head pointer, the function must use one of the given approaches, we can't use any of those approaches here.
Solution
We explicitly handle the case when the node to be deleted is the first node, we copy the data of the next node to the head and delete the next node. The cases when a deleted node is not the head node can be handled normally by finding the previous node and changing the next of the previous node. The following are the implementation.
C++
// C++ program to delete a given node
// in linked list under given constraints
#include <bits/stdc++.h>
using namespace std;
/* structure of a linked list node */
class Node
{
public:
int data;
Node *next;
};
void deleteNode(Node *head, Node *n)
{
// When node to be deleted is head node
if(head == n)
{
if(head->next == NULL)
{
cout << "There is only one node." <<
" The list can't be made empty ";
return;
}
/* Copy the data of next node to head */
head->data = head->next->data;
// store address of next node
n = head->next;
// Remove the link of next node
head->next = head->next->next;
// free memory
free(n);
return;
}
// When not first node, follow
// the normal deletion process
// find the previous node
Node *prev = head;
while(prev->next != NULL && prev->next != n)
prev = prev->next;
// Check if node really exists in Linked List
if(prev->next == NULL)
{
cout << "\nGiven node is not present in Linked List";
return;
}
// Remove node from Linked List
prev->next = prev->next->next;
// Free memory
free(n);
return;
}
/* Utility function to insert a node at the beginning */
void push(Node **head_ref, int new_data)
{
Node *new_node = new Node();
new_node->data = new_data;
new_node->next = *head_ref;
*head_ref = new_node;
}
/* Utility function to print a linked list */
void printList(Node *head)
{
while(head!=NULL)
{
cout<<head->data<<" ";
head=head->next;
}
cout<<endl;
}
/* Driver code */
int main()
{
Node *head = NULL;
/* Create following linked list
12->15->10->11->5->6->2->3 */
push(&head,3);
push(&head,2);
push(&head,6);
push(&head,5);
push(&head,11);
push(&head,10);
push(&head,15);
push(&head,12);
cout<<"Given Linked List: ";
printList(head);
/* Let us delete the node with value 10 */
cout<<"\nDeleting node "<< head->next->next->data<<" ";
deleteNode(head, head->next->next);
cout<<"\nModified Linked List: ";
printList(head);
/* Let us delete the first node */
cout<<"\nDeleting first node ";
deleteNode(head, head);
cout<<"\nModified Linked List: ";
printList(head);
return 0;
}
// This code is contributed by rathbhupendra
#include <stdio.h>
#include <stdlib.h>
/* structure of a linked list node */
struct Node
{
int data;
struct Node *next;
};
void deleteNode(struct Node *head, struct Node *n)
{
// When node to be deleted is head node
if(head == n)
{
if(head->next == NULL)
{
printf("There is only one node. The list can't be made empty ");
return;
}
/* Copy the data of next node to head */
head->data = head->next->data;
// store address of next node
n = head->next;
// Remove the link of next node
head->next = head->next->next;
// free memory
free(n);
return;
}
// When not first node, follow the normal deletion process
// find the previous node
struct Node *prev = head;
while(prev->next != NULL && prev->next != n)
prev = prev->next;
// Check if node really exists in Linked List
if(prev->next == NULL)
{
printf("\n Given node is not present in Linked List");
return;
}
// Remove node from Linked List
prev->next = prev->next->next;
// Free memory
free(n);
return;
}
/* Utility function to insert a node at the beginning */
void push(struct Node **head_ref, int new_data)
{
struct Node *new_node =
(struct Node *)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = *head_ref;
*head_ref = new_node;
}
/* Utility function to print a linked list */
void printList(struct Node *head)
{
while(head!=NULL)
{
printf("%d ",head->data);
head=head->next;
}
printf("\n");
}
/* Driver program to test above functions */
int main()
{
struct Node *head = NULL;
/* Create following linked list
12->15->10->11->5->6->2->3 */
push(&head,3);
push(&head,2);
push(&head,6);
push(&head,5);
push(&head,11);
push(&head,10);
push(&head,15);
push(&head,12);
printf("Given Linked List: ");
printList(head);
/* Let us delete the node with value 10 */
printf("\nDeleting node %d: ", head->next->next->data);
deleteNode(head, head->next->next);
printf("\nModified Linked List: ");
printList(head);
/* Let us delete the first node */
printf("\nDeleting first node ");
deleteNode(head, head);
printf("\nModified Linked List: ");
printList(head);
getchar();
return 0;
}
# Node class
class Node:
def __init__(self, data):
self.data = data
self.next = None
# LinkedList class
class LinkedList:
def __init__(self):
self.head = None
def deleteNode(self, data):
temp = self.head
prev = self.head
if temp.data == data:
if temp.next is None:
print("Can't delete the node as it has only one node")
else:
temp.data = temp.next.data
temp.next = temp.next.next
return
while temp.next is not None and temp.data != data:
prev = temp
temp = temp.next
if temp.next is None and temp.data !=data:
print("Can't delete the node as it doesn't exist")
# If node is last node of the linked list
elif temp.next is None and temp.data == data:
prev.next = None
else:
prev.next = temp.next
# To push a new element in the Linked List
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
# To print all the elements of the Linked List
def PrintList(self):
temp = self.head
while(temp):
print(temp.data, end = " ")
temp = temp.next
# Driver Code
llist = LinkedList()
llist.push(3)
llist.push(2)
llist.push(6)
llist.push(5)
llist.push(11)
llist.push(10)
llist.push(15)
llist.push(12)
print("Given Linked List: ", end = ' ')
llist.PrintList()
print("\n\nDeleting node 10:")
llist.deleteNode(10)
print("Modified Linked List: ", end = ' ')
llist.PrintList()
print("\n\nDeleting first node")
llist.deleteNode(12)
print("Modified Linked List: ", end = ' ')
llist.PrintList()
# This code is contributed by Akarsh Somani
// Java program to delete a given node
// in linked list under given constraints
class LinkedList {
static Node head;
static class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
void deleteNode(Node node, Node n) {
// When node to be deleted is head node
if (node == n) {
if (node.next == null) {
System.out.println("There is only one node. The list "
+ "can't be made empty ");
return;
}
/* Copy the data of next node to head */
node.data = node.next.data;
// store address of next node
n = node.next;
// Remove the link of next node
node.next = node.next.next;
// free memory
System.gc();
return;
}
// When not first node, follow the normal deletion process
// find the previous node
Node prev = node;
while (prev.next != null && prev.next != n) {
prev = prev.next;
}
// Check if node really exists in Linked List
if (prev.next == null) {
System.out.println("Given node is not present in Linked List");
return;
}
// Remove node from Linked List
prev.next = prev.next.next;
// Free memory
System.gc();
return;
}
/* Utility function to print a linked list */
void printList(Node head) {
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
System.out.println("");
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.head = new Node(12);
list.head.next = new Node(15);
list.head.next.next = new Node(10);
list.head.next.next.next = new Node(11);
list.head.next.next.next.next = new Node(5);
list.head.next.next.next.next.next = new Node(6);
list.head.next.next.next.next.next.next = new Node(2);
list.head.next.next.next.next.next.next.next = new Node(3);
System.out.println("Given Linked List :");
list.printList(head);
System.out.println("");
// Let us delete the node with value 10
System.out.println("Deleting node :" + head.next.next.data);
list.deleteNode(head, head.next.next);
System.out.println("Modified Linked list :");
list.printList(head);
System.out.println("");
// Let us delete the first node
System.out.println("Deleting first Node");
list.deleteNode(head, head);
System.out.println("Modified Linked List");
list.printList(head);
}
}
// this code has been contributed by Mayank Jaiswal
// C# program to delete a given
// node in linked list under
// given constraints
using System;
public class LinkedList
{
Node head;
class Node
{
public int data;
public Node next;
public Node(int d)
{
data = d;
next = null;
}
}
void deleteNode(Node node, Node n)
{
// When node to be deleted is head node
if (node == n)
{
if (node.next == null)
{
Console.WriteLine("There is only one node. The list "
+ "can't be made empty ");
return;
}
/* Copy the data of next node to head */
node.data = node.next.data;
// store address of next node
n = node.next;
// Remove the link of next node
node.next = node.next.next;
// free memory
GC.Collect();
return;
}
// When not first node, follow
// the normal deletion process
// find the previous node
Node prev = node;
while (prev.next != null && prev.next != n)
{
prev = prev.next;
}
// Check if node really exists in Linked List
if (prev.next == null)
{
Console.WriteLine("Given node is not" +
"present in Linked List");
return;
}
// Remove node from Linked List
prev.next = prev.next.next;
// Free memory
GC.Collect();
return;
}
/* Utility function to print a linked list */
void printList(Node head)
{
while (head != null)
{
Console.Write(head.data + " ");
head = head.next;
}
Console.WriteLine("");
}
// Driver code
public static void Main(String[] args)
{
LinkedList list = new LinkedList();
list.head = new Node(12);
list.head.next = new Node(15);
list.head.next.next = new Node(10);
list.head.next.next.next = new Node(11);
list.head.next.next.next.next = new Node(5);
list.head.next.next.next.next.next = new Node(6);
list.head.next.next.next.next.next.next = new Node(2);
list.head.next.next.next.next.next.next.next = new Node(3);
Console.WriteLine("Given Linked List :");
list.printList(list.head);
Console.WriteLine("");
// Let us delete the node with value 10
Console.WriteLine("Deleting node :" +
list.head.next.next.data);
list.deleteNode(list.head, list.head.next.next);
Console.WriteLine("Modified Linked list :");
list.printList(list.head);
Console.WriteLine("");
// Let us delete the first node
Console.WriteLine("Deleting first Node");
list.deleteNode(list.head, list.head);
Console.WriteLine("Modified Linked List");
list.printList(list.head);
}
}
// This code is contributed by Rajput-Ji
<script>
// javascript program to delete a given node
// in linked list under given constraints
var head;
class Node
{
constructor(val)
{
this.data = val;
this.next = null;
}
}
function deleteNode( node, n)
{
// When node to be deleted is head node
if (node == n)
{
if (node.next == null)
{
document.write("There is only one node. The list " + "can't be made empty ");
return;
}
/* Copy the data of next node to head */
node.data = node.next.data;
// store address of next node
n = node.next;
// Remove the link of next node
node.next = node.next.next;
// free memory
return;
}
// When not first node, follow the normal deletion process
// find the previous node
prev = node;
while (prev.next != null && prev.next != n)
{
prev = prev.next;
}
// Check if node really exists in Linked List
if (prev.next == null)
{
document.write("Given node is not present in Linked List");
return;
}
// Remove node from Linked List
prev.next = prev.next.next;
return;
}
/* Utility function to print a linked list */
function printList( head)
{
while (head != null)
{
document.write(head.data + " ");
head = head.next;
}
document.write("");
}
head = new Node(12);
head.next = new Node(15);
head.next.next = new Node(10);
head.next.next.next = new Node(11);
head.next.next.next.next = new Node(5);
head.next.next.next.next.next = new Node(6);
head.next.next.next.next.next.next = new Node(2);
head.next.next.next.next.next.next.next = new Node(3);
document.write("Given Linked List :");
printList(head);
document.write("");
// Let us delete the node with value 10
document.write("<br/>Deleting node :" + head.next.next.data);
deleteNode(head, head.next.next);
document.write("<br/>Modified Linked list :");
printList(head);
document.write("<br/>");
// Let us delete the first node
document.write("Deleting first Node<br/>");
deleteNode(head, head);
document.write("Modified Linked List");
printList(head);
// This code is contributed by todaysgaurav
</script>
Output:
Given Linked List: 12 15 10 11 5 6 2 3
Deleting node 10:
Modified Linked List: 12 15 11 5 6 2 3
Deleting first node
Modified Linked List: 15 11 5 6 2 3
TIme Complexity: O(n)
As we are traversing the list only once.
Auxiliary Space: O(1)
As constant extra space is used.
Please write comments if you find the above codes/algorithms incorrect, or find other ways to solve the same problem.
Similar Reads
Delete continuous nodes with sum K from a given linked list
Given a singly linked list and an integer K, the task is to remove all the continuous set of nodes whose sum is K from the given linked list. Print the updated linked list after the removal. If no such deletion can occur, print the original Linked list. Examples: Input: Linked List: 1 -> 2 ->
11 min read
Insert a Node after a given Node in Linked List
Given a linked list, the task is to insert a new node after a given node of the linked list. If the given node is not present in the linked list, print "Node not found".Examples:Input: LinkedList = 2 -> 3 -> 4 -> 5, newData = 1, key = 2Output: LinkedList = 2 -> 1 -> 3 -> 4 -> 5I
11 min read
Insert a Node before a given node in Doubly Linked List
Given a Doubly Linked List, the task is to insert a new node before a given node in the linked list.Examples: Input: Linked List = 1 <-> 3 <-> 4, newData = 2, key = 3Output: Linked List = 1 <-> 2 <-> 3 <-> 4Explanation: New node with data 2 is inserted before the node w
12 min read
Insert a Node after a given node in Doubly Linked List
Given a Doubly Linked List, the task is to insert a new node after a given node in the linked list.Examples: Input: Linked List = 1 <-> 2 <-> 4, newData = 3, key = 2Output: Linked List = 1 <-> 2 <-> 3 <-> 4Explanation: New node 3 is inserted after key, that is node 2.In
11 min read
Delete a Linked List node at a given position
Given a singly linked list and a position (1-based indexing), the task is to delete a linked list node at the given position.Note: Position will be valid (i.e, 1 <= position <= linked list length)Example: Input: position = 2, Linked List = 8->2->3->1->7Output: Linked List = 8->3
8 min read
Delete a Doubly Linked List node at a given position
Given a doubly linked list and a position pos, the task is to delete the node at the given position from the beginning of Doubly Linked List.Input: LinkedList: 1<->2<->3, pos = 2Output: LinkedList: 1<->3Input: LinkedList: 1<->2<->3, pos = 1Output: LinkedList: 2<->
9 min read
Deletion at end (Removal of last node) in a Linked List
Given a linked list, the task is to delete the last node of the given linked list.Examples:Â Â Input: 1 -> 2 -> 3 -> 4 -> 5 -> NULLOutput: 1 -> 2 -> 3 -> 4 -> NULL Explanation: The last node of the linked list is 5, so 5 is deleted. Input: 3 -> 12 -> 15-> NULLOutput
8 min read
Delete all occurrences of a given key in a linked list
Given a singly linked list, the task is to delete all occurrences of a given key in it.Examples:Input: head: 2 -> 2 -> 1 -> 8 -> 2 -> NULL, key = 2Output: 1 -> 8 -> NULL Explanation: All occurrences of the given key = 2, is deleted from the Linked ListInput: head: 1 -> 1 -
8 min read
Delete all the even nodes of a Circular Linked List
Given a circular singly linked list containing N nodes, the task is to delete all the even nodes from the list. Examples: Input : 57->11->2->56->12->61 Output : List after deletion : 57 -> 11 -> 61 Input : 9->11->32->6->13->20 Output : List after deletion : 9 -
10 min read
Delete alternate nodes of a Linked List
Given a Singly Linked List, starting from the second node delete all alternate nodes of it. For example, if the given linked list is 1->2->3->4->5 then your function should convert it to 1->3->5, and if the given linked list is 1->2->3->4 then convert it to 1->3. Recomm
14 min read