Delete Node without head pointer of the Linked List

Delete Node without head pointer of the Linked List” is a tricky problem based on linked list data structure asked in many technical interview.

Here, We are given a node address of a node to be deleted from the linked list and Our task is to delete that node. The head of the linked list is not given. 

Note: It is assumed that the node to be deleted is not the last node of the linked list.

The steps required to delete node without head pointer are as follows:

  1. As we already know that the node to be deleted is not a last node, we will swap the data value of current node with the data value of next node.
  2. And then delete the next node.

C++ Program to delete node without head pointer is as follows:

/* C++ Program to Delete node without head pointer */
#include<bits/stdc++.h>
using namespace std;

/* Structure of the node of the linked list */
struct node
{
    int data;
    struct node *next;
};

/* Function to insert node at the end of the linked list */
void insert_end(struct node **head, int ele)
{
    /* Creating a new node */
    struct node *new_node;
    new_node = (struct node*)malloc(sizeof(struct node));
    new_node->data = ele;
    new_node->next = NULL;
    
    /* Check whether the linked list is empty or not */
    
    /* If the linked list is empty, then new node will become head of the linked list */
    if(*head == NULL)    
    {
        *head = new_node;
        return;
    }
    
    /* If the linked list is not empty, then traverse the complete linked list and point the
       pointer of the last node of the linked list to the new node*/
    struct node *temp = NULL;
    temp = (*head);
    while(temp->next != NULL)
    temp=temp->next;
    temp->next = new_node;
}

/* Function to delete given node of the linked list */
void deleteNode(struct node *Node)
{
    /*
    As we already know, the node to be deleted is not last node, so 
    swap the data of given node with the data of next node. Then, delete
    the next node of the linked list
    */
    int temp = Node -> data;
    Node -> data = Node -> next -> data;
    Node -> next ->data = temp;
    Node -> next = Node -> next -> next;
    delete (Node->next);
}

/*
Function to print the linked list
*/
void print(struct node *head)
{
    struct node *temp = head;
    while(temp!=NULL)
    {
        cout<<temp->data<<" ";
        temp=temp->next;
    }
}
int main()
{
    struct node *head;
    head = NULL;
    /* Insert Some Nodes in the Linked List */
    insert_end(&head,4);
    insert_end(&head,3);
    insert_end(&head,2);
    insert_end(&head,1);
    cout<<"Before deleting 3rd node\n";
    print(head);
    deleteNode(head->next->next);
    cout<<"\nAfter deleting 3rd node\n";
    print(head);
}
OUTPUT:
Before deleting 3rd node
4 3 2 1
After deleting 3rd node
4 3 1

Related Posts:

  1. Delete Complete Linked List.
  2. Delete Nth Node of the Linked List.
  3. Delete All Occurrences of particular node of the Linked List.
  4. Delete Alternate Nodes of the Linked List.
  5. Delete every ‘N’ Nodes After ‘M’ Nodes of the Linked List.
  6. Remove Duplicate Nodes from an Unsorted Linked List.
  7. Remove Duplicate Nodes from a Sorted Linked List.
  8. Find Union and Intersection of Two Linked List.
  9. Merge Two Sorted Linked List.
  10. Insert a New Node at the Middle of the Linked List.
  11. Insert a New Node at the Sorted Linked List.
  12. Reverse a Linked List.
  13. Reverse a Linked List Using Stack.
  14. Printing Linked List in Reverse Order without actually reversing the Linked List.
  15. Swap Adjacent Elements of the Linked List.
  16. Count All Occurrences of a Particular Node in a Linked List.
  17. Bubble Sort on Linked List.
  18. Detect a Loop in a Linked List.
  19. Find the Length of the Loop present in the Linked List.
  20. Detect and Remove Loop from a Linked List.

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *