Thursday, September 1, 2011

Deleting a node from a singly linked list

Deleting a node from a singly linked list

//this case works only when marked node is not the last node


struct node{
    int val;
    struct node * next;
};


bool delete (struct node * mark)
{
    bool deleted = false;
    
    if(mark && mark->next)
    {
        struct node * new_mark = mark->next;
        mark->next = new_mark->next;
        mark->val = new_mark->val;
        
        new_mark->next = NULL;
        free( new_mark );
        new_mark = NULL;
        
        deleted = true;
    }
    else
    {
        //need head for this case
    }
    
    return deleted;
}


// this works even if node to be deleted is last node


struct node{
    int val;
    struct node * next;
};


bool delete (struct node* head, struct node * mark)
{
    bool deleted = false;
    
    //mark and head could be same here or different. But mark->next is not null
    if(mark && mark->next)
    {
        struct node * new_mark = mark->next;
        mark->next = new_mark->next->next;
        mark->val = new_mark->val;
        
        new_mark->next = NULL;
        free( new_mark );
        new_mark = NULL;
        
        deleted = true;
    }
    // here mark->next is null and mark is head, so we can just go ahead and delete it
    else if(mark && !(mark->next) && mark == head)
    {
        free( mark );
        mark = NULL;
        head = NULL;
        deleted = true;
    }
    //here mark is the last node and its not same as head, so now we need to iterate
    else //( mark && !(mark->next) && mark != head )
    {
        struct node * iter = head;
        //iterate until last but one node
        while( iter && (iter->next!=mark) )
        {
            iter = iter->next;
        }
        
        //make sure we are at a node whose next node is mark
        if(iter && (iter->next == mark) )
        {
            free(mark);
            mark = NULL;
            iter->next = NULL;
            deleted = true;
        }
        else
        {
            //sorry mark is not in the list that starts with head
        }
    }
    
    return deleted;
}



No comments: