CODEWITHSUNDEEP
c++
user3259711
user3259711

Reputation: 49

delete a node in the middle of a single linked list, given only access to that node

This is an interview question in "Cracking the coding interview". My code and test cases are here:

#include<iostream>
using namespace std;

struct node
{
    int data;
    node* next;
};
node* init(int a[], int n);
void remove(node* & c);
void printList(node* head);

int main()
{
    int a[]={0,1,2,3,4,5,6,7,8,9};
    node* testHead=init(a, 10);
    printList(testHead);
    cout<<endl;
    int nth=9;
    node *c=testHead;
    for(int i=0; i<nth; i++)
    {
        c=c->next;
    }
    remove(c);
    printList(testHead);
    system("PAUSE");
    return 0;
}

node* init(int a[], int n)
{
    node *head, *p;
    for(int i=0; i<n; i++)
    {
        node *nd=new node();
        nd->data=a[i];
        if(i==0)
        {
            head=nd;
            p=nd;
        }
        else
        {
            p->next=nd;
            p=nd;
        }
    }
    return head;
}

void remove(node* & c)
{
    if(c==NULL)
        return;
    node* tmp=c->next;
    if(tmp==NULL)
    {
        delete c;
        c=NULL;
    }
    else
    {
        c->data=tmp->data;
        c->next=tmp->next;
        delete tmp;
    }
}

void printList(node* head)
{
    while(head!=NULL)
    {
        cout<<head->data<<" ";
        head=head->next;
    }
}

Here in the main function, I tried to delete the last node, with the data value 9. However, even in the function "remove", I checked the last node and if it is, I set it to NULL, the output will produce an error. Can anyone tell me why this happen?

Thanks.

Upvotes: 0

Views: 1956

Answers (2)

Abhishek Bansal
Abhishek Bansal

Reputation: 12715

The problems are actually as follows:

  1. You should make the last node of list point to NULL while building the list.
  2. When you delete the last node in the linked list, the previous node -> next becomes a dangling pointer. This pointer has to be made to point to NULL. Since you do not have its address, you will again have to traverse this list from the head node till you get the address of the node prior to the node to be deleted.

Upvotes: 1

tecardo at HoN
tecardo at HoN

Reputation: 23

void remove(node* & c) // --> 1
{
    if(c==NULL)
       return;
    node* tmp=c->next;
    if(tmp==NULL)
    {
        delete c; // --> 2
        c=NULL; // --> 3
    }
    else
    {
        c->data=tmp->data;
        c->next=tmp->next;
        delete tmp;
    }
}

This is the thing:

  1. When you pass in as a pointer, you does not necessary to pass in as a reference. It is redundant. //Check @WhozCraig comment for correction
  2. delete releases c allocated memory
  3. Therefore, you cannot assign a NULL to c

Other word, how can you assign NULL to a variable that has been released?

Upvotes: 0

Related Questions