Delete Nth Node of the Linked List

Delete Nth Node of the Linked List” is a basic problem exercise for beginners based on linked list. Here, we are given a linked list and our task to delete nth position node.

To do so, we need to traverse the linked list to the node just before the nth node, then change the pointer of that node to next to next node and then delete the nth node.

For example, we need to delete the 2nd node from the following linked list.

delete nth node of the linked list
Delete nth node of the linked list

The steps required to delete the nth node from the linked list are as follows:

  1. If Linked List is empty, simply return.
  2. If the Node to be deleted is first node, then make head of the linked list to the second node. If second node does not exist(linked list is empty), then mark head of the Linked List to NULL.
  3. If the node to be deleted is not first node, then, traverse linked list to nth node of the linked list and mark pointer to just before the nth node know as ‘previous’ node.
  4. Then, point the pointer of previous node to the next of nth node of the linked list.
  5. Lastly, delete nth node of the linked list.

C++ Program to delete Nth node of the linked list is as follows:

/* Program to delete nth node of the linked list */
#include<bits/stdc++.h>
using namespace std;

/* Structure of 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 Linked List is empty */
    if(*head == NULL)    
    {
        *head = new_node;
        return;
    }
    
    /* If Linked List is not empty, then traverse the linked list 
    and point the pointer of the last node to the new node*/
    struct node *temp = NULL;
    temp = (*head);
    while(temp->next != NULL)
    temp=temp->next;
    temp->next = new_node;
}

/* Function to delete Nth Node of the Linked List */
void deleteNth(struct node **head,int n)
{
    /* If Linked List is empty,  there is no node to delete, hence return */
    if( *head == NULL)  
    return;
    struct node *temp = *head , *prev = NULL;
    /* If first node is to be deleted, then mark the head to 
    the next of first node, and delete first node*/
    if(n==1) 
    {
        (*head) = (*head) -> next; 
        delete temp;
        return;
    }
    int i;
    /* For Nth Node to be deleted, traverse the linked list to Nth node and store the pointer 
    to (n-1)th node, after that mark the pointer of (n-1)th node to the next of nth node. Then,
    delete Nth Node */
    for(i = 1; i < n && temp!=NULL; i++)
    {
        prev = temp;
        temp=temp->next;
    }
    if(i < n)
    return; // there are less number of nodes
    prev->next = temp->next;
    delete temp;
}

/* Function to print Nth Node*/
void print(struct node *head)
{
    struct node *p = head;
    while(p!=NULL)
    {
        cout<<p->data<<" ";
        p=p->next;
    }
}
int main()
{
    struct node *head;
    head = NULL;
    /* Inserting Some Nodes in the Linked List */
    insert_end(&head,1);
    insert_end(&head,2);
    insert_end(&head,3);
    insert_end(&head,4);
    cout<<"The linked list elements before deleting 3rd node: \n";
    print(head);
    deleteNth(&head,3);
    cout<<"\n The linked list elements after deleting 3rd node: \n";
    print(head);
}
OUTPUT:
The linked list elements before deleting 3rd node:
1 2 3 4
The linked list elements after deleting 3rd node:
1 2 4

Related Posts:

  1. Delete Complete Linked List.
  2. Delete without head pointer 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 Sorted Linked List.
  11. Reverse a Linked List.
  12. Reverse a Linked List Using Stack.
  13. Printing Linked List in Reverse Order without actually reversing the Linked List.
  14. Swap Adjacent Elements of the Linked List.
  15. Count All Occurrences of a Particular Node in a Linked List.
  16. Bubble Sort on Linked List.
  17. Detect a Loop in a Linked List.
  18. Find the Length of the Loop present in the Linked List.
  19. Detect and Remove Loop from a Linked List.
  20. Segregate Even and Odd Nodes of the Linked List.

You may also like...

Leave a Reply

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