Home » Interview Questions » LinkedList Interview Questions » Delete a node under given conditions

Delete a node under given conditions


()

In the given linked list write a function to delete a given node. Under conditions :

a) Parameter of function are pointer to the start node and node to be deleted.

b) Should not accept pointer to head node, should not return pointer to head node.(Linked list never become empty)

Algorithm

There are two possibilities either we need to delete head node or we need to delete any other node.

a. When we are deleting node other than head node, we delete normally by keeping track of previous node and changing next of previous node.

b. If we want to delete head node, we cannot just change the pointer of head to head->next.

c. We should copy data of next node to head, change the next of head and remove the link of next node.

d. Delete next to head.

Algorithm working

C++ Program

#include <bits/stdc++.h>

using namespace std;

struct LLNode
{
    int data;
    struct LLNode *next;
};
 
void DeleteNode(struct LLNode *head, struct LLNode *nodeToBeDeleted)
{
    //Node to be deleted is start node
    if(head == nodeToBeDeleted)
    {
        //only single node
        if(head->next == NULL)
        {
            cout<<"list can`t be empty"<<endl;
            return;
        }
        //code data of next node to head
        //delete next 
        //change head->next to head->next->next 
        head->data = head->next->data;
        nodeToBeDeleted = head->next;
        head->next = head->next->next;
        free(nodeToBeDeleted);
        return;
    }
    //Delete node other than head
    //use normal deletion method
    struct LLNode *prev = head;
    while(prev->next != NULL && prev->next != nodeToBeDeleted)
    {
        prev = prev->next;
    }
    if(prev->next == NULL)
    {
        cout<<"Invalid input!"<<endl;
        return;
    }
    prev->next = prev->next->next;
    free(nodeToBeDeleted);
    return; 
}
 /* Function to insertAtBeginning a node */
void insertAtBeginning(struct LLNode** head, int dataToBeInserted)
{
    struct LLNode* curr = new LLNode;
    curr->data = dataToBeInserted;
    curr->next = NULL;    
    if(*head == NULL)
            *head=curr; //if this is first node make this as head of list
        
    else
        {
            curr->next=*head; //else make the curr (new) node's next point to head and make this new node a the head
            *head=curr;
        }
        
        //O(1) constant time
}
 
//display linked list
void display(struct LLNode**node)
{
    struct LLNode *temp= *node;
    while(temp!=NULL)
        {
            if(temp->next!=NULL)
            cout<<temp->data<<"->";
            else
            cout<<temp->data;
            
            temp=temp->next; //move to next node
        }
        //O(number of nodes)
    cout<<endl;
}
 
//Main function
int main()
{
    struct LLNode *head = NULL;
    insertAtBeginning(&head,17);
    insertAtBeginning(&head,13);
    insertAtBeginning(&head,11);
    insertAtBeginning(&head,3);
    insertAtBeginning(&head,4);
    insertAtBeginning(&head,13);
    insertAtBeginning(&head,7);
 
    cout<<"Input linked List: ";
    display(&head);
    cout<<"a)"<<endl;
    cout<<"Delete node: "<<head->next->next->data;
    DeleteNode(head, head->next->next);
 
    cout<<"\nOutput linked list: ";
    display(&head);
    cout<<endl;
    cout<<"b)"<<endl;
    /* Let us delete the the first node */
    cout<<"Delete start node:"<<head->data;
    DeleteNode(head, head);
 
    cout<<"\nOutput linked list: ";
    display(&head);
    return 0;
}

READ  Merge Two Sorted Lists Leetcode

 

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions