Linked List: Delete Node

Question: You are given a pointer to a node in a singly linked list. The head pointer is not available. Your task is to delete the specified node.

Solution: Typically, deleting a node from a singly linked list requires us to have the pointer to the node before the node to be deleted. We need this previous pointer so we can set it's Next pointer to the node after the specified node to be deleted. In this problem since we do not have the head pointer, we cannot walk the list and get the previous pointer.

We need to start thinking about what information does a linked list node have. Typically it has one or more data variables and a Next pointer that points to the next node in the linked list. If we were to overwrite the data in the specified node to be deleted from the next node in the list and delete this next node instead of the specified node, we would have effectively deleted the node. Technically, we don't delete the specified node but delete the next node after we copy data from it.

Note: This approach does not work in the case where the specified node to be deleted is the last node in the linked list.

Code: typedef struct _node

{
 int i;
 struct _node *next;
} Node;

void DeleteNode(Node *deleteThisNode)
{
  if(deleteThisNode->next != null)                  //only if the specified node is not the last node of the list
                                                    // this approach does not work in that case
  {
      deleteThisNode->i = deleteThisNode->next->i;  //copy data from the next node
      Node * freeThis = deleteThisNode->next;       //save the ptr to the next node, so we can free it
      deleteThisNode->next = deleteThisNode->next->next;  //point the Next pointer to the node after deleteThisNode->next
      free(freeThis);                               //don't forget to free memory
  }
}