Question

Assume that you have a linked list of records. Assume that you have a head, a current, and a tail pointer. Write an algorithm that DELETES the node BEFORE the current node. You can use pseudo-code, English or drawing to describe your solution.( this was, and remains to be, a popular technical interview question)

Answer 1

/*
We want to delete the node before the CURRENT node....

LOGIC :
   Traverse the head node until we go to the node, just before the current node.
   Then we have to copy the record of current Node and overwrites on the before node's record. (as same as deleting the before Node)
   Then we can just delete the Current node....

Time Complexity : O(n)
Space Complexity : O(1)
*/

/* C Programming */
struct node
{
   int record; /* records can be any more*/
   struct node *next; /* points to next record*/
};

/*Actual Psuedo code */
void deleteNode(struct node *head, struct node *current, struct node *tail)
{  
  
   if(head == current)
   {
       printf(" We are unable to delete the before node to Head");
       return;
   }
  
   /* Assume 'tail' is the last node. So, its 'next' must be NULL*/
  
   while(head != tail->next)
   {
       if(head->next == current)
       {
           /* record of current Node will overwrites the before node's record.
               this would be as same as deleting the before Node*/
          
           head->record = current->record; /* we can do it for all the data in the record*/
          
           /* deleting the current node*/
          
           head->next = current->next;
          
           free(current);
       }
      
       head=head->next;
   }
  
   if(head == NULL)
       printf("current node is not found in the list");
}