Delete a node from linked list without head pointer in Java

Delete a node from linked list without head pointer in Java

Delete a Node from linked list without head pointer

You are given a singly linked list and pointer which is pointing to the node which is required to be deleted. Any information about head pointer or any other node is not given. You need to write a function to delete that node from linked list. Your function will take only one argument: pointer to the node which is to be deleted.

Note: No head reference is given to you.
It is guaranteed that the node to be deleted is not the last node;

Examples:
A linked list is built as:

Defination of each node is as follows: struct Node { int data; struct Node* next; }; Input : C (a pointer to C) Output : A–>B–>D–>E–>F Input : A (a pointer to A) Output : B–>D–>E–>F

It would be a simple deletion problem from the singly linked list if the head pointer was given because for deletion you must know the previous node and you can easily reach there by traversing from the head pointer. Conventional deletion is impossible without knowledge of the previous node of a node that needs to be deleted.
The trick here is we can copy the data of the next node to the data field of the current node to be deleted. Then we can move one step forward. Now our next has become the current node and the current has become the previous node. Now we can easily delete the current node by conventional deletion methods.
For example, suppose we need to delete C and a pointer to C is given. If we had a pointer to B we could have deleted C easily. But here we will copy the data field of D to the data field of C. Then we will move forward. Now we are at D and we have a pointer to C i.e. the previous pointer. So we will delete D. That’s how node C will be deleted.
Below image is a dry run of the above approach:

Below is the implementation of the above approach :

CPP

// C++ program to delete a node

#include <bits/stdc++.h>

using namespace std;

/* Link list node */

struct Node {

int data;

struct Node* next;

};

// Function to delete the node without head

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;

// Perform conventional deletion

pos->next = pos->next->next;

free(temp);

}

}

// Function to print the linked list

void print(Node* head)

{

Node* temp = head;

while (temp) {

cout << temp->data << ” -> “;

temp = temp->next;

}

cout << “NULL”;

}

void push(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;

}

// Driver Code

int main()

{

/* Start with the empty list */

struct Node* head = NULL;

// create linked 35->15->4->20

push(&head, 20);

push(&head, 4);

push(&head, 15);

push(&head, 35);

cout << “Initial Linked List: \n”;

print(head);

cout << endl << endl;

// Delete 15 without sending head

Node* del = head->next;

deleteNodeWithoutHead(del);

// Print the final linked list

cout << “Final Linked List after deletion of 15:\n”;

print(head);

return 0;

// This code has been contributed by Striver

}

Output:
Initial Linked List: 35 -> 15 -> 4 -> 20 -> NULL Final Linked List after deletion of 15: 35 -> 4 -> 20 -> NULL

This article is contributed by Jeet Jain. Please see Given only a pointer to a node to be deleted in a singly linked list, how do you delete it? for more details and complete implementation.

Article Tags :

Linked List

Technical Scripter

MAQ Software

programming-puzzle

Technical Scripter 2018

Practice Tags :

MAQ Software

Linked List

Baca Juga :   Suatu alat yang dapat mengubah getaran listrik menjadi gerak dinamakan

Given only a pointer to a node to be deleted in a singly linked list, how do you delete it?

A
simple solution
is to traverse the linked list until you find the node you want to delete. But this solution requires a pointer to the head node which contradicts the problem statement.

The
fast solution
is to copy the data from the next node to the node to be deleted and delete the next node. Something like this:

It is important to note that this approach will only work if it is
guaranteed
that the given pointer does
not
point to the
last node. Because if it is the last node, then you don’t have a next node to copy the data from.

struct Node *temp = node_ptr->next; node_ptr->data = temp->data; node_ptr->next = temp->next; free(temp);

Below is the implementation of the above code:

C++

// C++ program to del the node

// in which only a single pointer

// is known pointing to that node

#include <assert.h>

#include <bits/stdc++.h>

using namespace std;

/* Link list node */

class Node {

public:

int data;

Node* next;

};

/* Given a reference (pointer to pointer) to the head

of a list and an int, push a new node on the front

of the list. */

void push(Node** head_ref, int new_data)

{

/* allocate node */

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;

}

void printList(Node* head)

{

Node* temp = head;

while (temp != NULL) {

cout << temp->data << ” “;

temp = temp->next;

}

}

void deleteNode(Node* node_ptr)

{

// If the node to be deleted is the

// last node of linked list

if (node_ptr->next == NULL)

{

free(node_ptr);

// this will simply make the node_ptr NULL.

return;

}

// if node to be deleted is the first or

// any node in between the linked list.

Node* temp = node_ptr->next;

node_ptr->data = temp->data;

node_ptr->next = temp->next;

free(temp);

}

// Driver code

int main()

{

/* Start with the empty list */

Node* head = NULL;

/* Use push() to construct below list

1->12->1->4->1 */

push(&head, 1);

push(&head, 4);

push(&head, 1);

push(&head, 12);

push(&head, 1);

cout << “Before deleting \n”;

printList(head);

/* I m deleting the head itself.

You can check for more cases */

deleteNode(head);

cout << “\nAfter deleting \n”;

printList(head);

return 0;

}

// This code is contributed by rathbhupendra

C

// C++ program to del the node

// in which only a single pointer

// is known pointing to that node

#include <assert.h>

#include <stdio.h>

#include <stdlib.h>

/* Link list node */

struct Node {

int data;

struct Node* next;

};

/* Given a reference (pointer to pointer) to the head

of a list and an int, push a new node on the front

of the list. */

void push(struct Node** head_ref, int new_data)

{

/* allocate node */

struct Node* new_node

= (struct Node*)malloc(sizeof(struct 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;

}

void printList(struct Node* head)

{

struct Node* temp = head;

while (temp != NULL) {

printf(“%d “, temp->data);

temp = temp->next;

}

}

void deleteNode(struct Node* node_ptr)

{

// If the node to be deleted is the last

// node of linked list

if (node_ptr->next == NULL)

{

free(node_ptr);

// this will simply make the node_ptr NULL.

return;

}

struct Node* temp = node_ptr->next;

node_ptr->data = temp->data;

node_ptr->next = temp->next;

free(temp);

}

// Driver code

int main()

{

/* Start with the empty list */

struct Node* head = NULL;

/* Use push() to construct below list

1->12->1->4->1 */

push(&head, 1);

push(&head, 4);

push(&head, 1);

push(&head, 12);

push(&head, 1);

printf(“\n Before deleting \n”);

printList(head);

/* I m deleting the head itself.

You can check for more cases */

deleteNode(head);

printf(“\n After deleting \n”);

printList(head);

getchar();

}

Java

// Java program to del the node in

// which only a single pointer is

// known pointing to that node

class LinkedList {

static Node head;

static class Node {

int data;

Node next;

Node(int d)

{

data = d;

next = null;

}

}

void printList(Node node)

{

while (node != null) {

System.out.print(node.data + ” “);

node = node.next;

}

}

void deleteNode(Node node)

{

Node temp = node.next;

node.data = temp.data;

node.next = temp.next;

System.gc();

}

// Driver code

public static void main(String[] args)

{

LinkedList list = new LinkedList();

list.head = new Node(1);

list.head.next = new Node(12);

list.head.next.next = new Node(1);

list.head.next.next.next = new Node(4);

list.head.next.next.next.next = new Node(1);

System.out.println(“Before Deleting “);

list.printList(head);

/* I m deleting the head itself.

You can check for more cases */

list.deleteNode(head);

System.out.println(“”);

System.out.println(“After deleting “);

list.printList(head);

}

}

// This code has been contributed by Mayank Jaiswal

Python3

# A python3 program to delete

# the node in which only a single pointer

# is known pointing to that node

# Linked list node

class Node():

def __init__(self):

self.data = None

self.next = None

# Given a reference (pointer to pointer)

# to the head of a list and an int,

# push a new node on the front of the list

def push(head_ref, new_data):

# allocate node

new_node = 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

return head_ref

def printList(head):

temp = head

while(temp != None):

print(temp.data, end=’ ‘)

temp = temp.next

def deleteNode(node_ptr):

temp = node_ptr.next

node_ptr.data = temp.data

node_ptr.next = temp.next

# Driver code

if __name__ == ‘__main__’:

# Start with the empty list

head = None

# Use push() to construct below list

# 1->12->1->4->1

head = push(head, 1)

head = push(head, 4)

head = push(head, 1)

head = push(head, 12)

head = push(head, 1)

print(“Before deleting “)

printList(head)

# I’m deleting the head itself.

# You can check for more cases

deleteNode(head)

print(“\nAfter deleting”)

printList(head)

# This code is contributed by Yashyasvi Agarwal

C#

// C# program to del the node in

// which only a single pointer is

// known pointing to that node

using System;

public class LinkedList {

Node head;

public class Node {

public int data;

public Node next;

public Node(int d)

{

data = d;

next = null;

}

}

void printList(Node node)

{

while (node != null) {

Console.Write(node.data + ” “);

node = node.next;

}

}

void deleteNode(Node node)

{

Node temp = node.next;

node.data = temp.data;

node.next = temp.next;

}

// Driver code

public static void Main()

{

LinkedList list = new LinkedList();

list.head = new Node(1);

list.head.next = new Node(12);

list.head.next.next = new Node(1);

list.head.next.next.next = new Node(4);

list.head.next.next.next.next = new Node(1);

Console.WriteLine(“Before Deleting “);

list.printList(list.head);

/* I m deleting the head itself.

You can check for more cases */

list.deleteNode(list.head);

Console.WriteLine(“”);

Console.WriteLine(“After deleting “);

list.printList(list.head);

}

}

/* This code contributed by PrinciRaj1992 */

Javascript

<script>

// javascript program to del the node in

// which only a single pointer is

// known pointing to that node

var head;

class Node{

constructor(val){

this.data = val;

this.next = null;

}

}

function printList(node){

while (node != null){

document.write(node.data + ” “);

node = node.next;

}

}

function deleteNode(node) {

var temp = node.next;

node.data = temp.data;

node.next = temp.next;

}

// Driver code

head = new Node(1);

head.next = new Node(12);

head.next.next = new Node(1);

head.next.next.next = new Node(4);

head.next.next.next.next = new Node(1);

document.write(“Before Deleting<br/> “);

printList(head);

/*

* I m deleting the head itself. You can check for more cases

*/

deleteNode(head);

document.write(“<br/>”);

document.write(“After deleting<br/> “);

printList(head);

// This code is contributed by todaysgaurav

</script>

Output

Before deleting 1 12 1 4 1 After deleting 12 1 4 1

To make this solution work, we can mark the end node as a dummy node. But the programs/functions that are using this function should also be modified.
Try this problem in a doubly-linked list.

Article Tags :

Linked List

Practice Tags :

Linked List

Delete a Node from linked list without head pointer in C++

C++
Server Side Programming
Programming

Baca Juga :   Apa yang dimaksud redistribusi pendapatan


In this tutorial, we are going to learn how to delete a node without head pointer in a singly linked list.

Let’s see the steps to solve the problem.

  • Write struct with data, and next pointer.

  • Write a function to insert the node into the singly linked list.

  • Initialize the singly linked list with dummy data.

  • Take a node from the linked list using the next pointer.

  • Move the delete node to the next node.

Delete a node from linked list without head pointer in python

Python program for Delete a node from linked list without head pointer. Here problem description and other solutions.

# Python 3 program for # Delete a node from linked list without head # Linked list node 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 # 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 = ” “) # Visit to next node temp = temp.next else : print(“Empty Linked list”) # 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 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) sll.addNode(6) sll.addNode(7) print(” Before delete node 3″) sll.display() # Delete node 3 sll.deleteNode(sll.head.next.next) print(“\n After delete node 3”) sll.display() if __name__ == “__main__”: main()

Baca Juga :   Bagaimana cara petani berinteraksi dengan alam ketika waktu tanam padi

Output

Before delete node 3 1 2 3 4 5 6 7 After delete node 3 1 2 4 5 6 7

Delete a node from linked list without head pointer in Java

Posted by: pskji.org