Interview Question
Given a linked list and a pointer to some node, delete that node. The catch is that the only pointer you are provided is of that node, you don't have access to even the head or first element of the list.
Solution
To successfully delete a node, we need to change the next pointer of previous node to point to to-be-deleted node's next node. Copy the data from the next node to the current node, and then delete the next node. A limitation of this approach is that you cannot delete the last node. To delete the last node, we need to modify the entire data structure to include a dummy node as the last node which is not part of the linked list.
#include <stdio.h>
#include <stdlib.h>
struct node {
int data ;
struct node * next ;
} * head = NULL ;
void push ( int val )
{
struct node * newnode = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
newnode -> data = val ;
newnode -> next = NULL ;
struct node * ptr = head ;
if ( ptr == NULL )
head = newnode ;
else
{
while ( ptr -> next )
ptr = ptr -> next ;
ptr -> next = newnode ;
}
}
void print ()
{
struct node * itr ;
itr = head ;
while ( itr )
{
printf ( " %d " , itr -> data ) ;
itr = itr -> next ;
}
}
void delNode ( struct node * del )
{
struct node * temp ;
del -> data = del -> next -> data ;
temp = del -> next ;
del -> next = temp -> next ;
free ( temp ) ;
}
int main ()
{
push ( 2 ) ;
push ( 3 ) ;
push ( 1 ) ;
push ( 8 ) ;
push ( 7 ) ;
print () ;
delNode( head -> next ) ;
printf ( " \n ") ;
print () ;
return 0 ;
}
