Tricky Interview#3 Solution

Question:

Given only a pointer/reference to a node to be deleted in a singly linked list, how do you delete it?

Solution:

Approach/Algorithm:

A simple solution is to traverse the linked list until you find the node you want to delete. But this solution requires a pointer to the head node which contradicts the problem statement.

The fast solution is to copy the data from the next node to the node to be deleted and delete the next node. 

    // Find next node using next pointer
    struct Node *temp  = node_ptr->next;

    // Copy data of next node to this node
    node_ptr->data  = temp->data;

    // Unlink next node
    node_ptr->next  = temp->next;

    // Delete next node
    free(temp);


C Program:


#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

struct Node
{
    int data;
    struct Node* next;
};

void push(struct Node** head_ref, int new_data)
{
   struct Node* new_node =
             (struct Node*) malloc(sizeof(struct Node));

   new_node->data  = new_data;

   new_node->next = (*head_ref);

   (*head_ref)= new_node;
}

void printList(struct Node *head)
{
   struct Node *temp = head;
   while(temp != NULL)
   {
      printf("%d  ", temp->data);
      temp = temp->next;
   }
}

void deleteNode(struct Node *node_ptr)
{
   struct Node *temp = node_ptr->next;
   node_ptr->data    = temp->data;
   node_ptr->next    = temp->next;
   free(temp);
}

int main()
{
    struct Node* head = NULL;

    /* Use push() to construct below list
    1->12->1->4->1  */
    push(&head, 1);
    push(&head, 4);
    push(&head, 1);
    push(&head, 12);
    push(&head, 1);

    printf("Before deleting \n");
    printList(head);

    deleteNode(head);

    printf("\nAfter deleting \n");
    printList(head);
    return 0;
}

Output:

Before deleting
1 12 1 4 1
After deleting
12 1 4 1

Note:
This solution doesn’t work if the node to be deleted is the last node of the list.