Delete the last node of a single linked list using the single pointer to start node

Question

Can I delete the last node using the below prototype in C -: int delete(struct node *head, int item)

Note-: The first argument here is a point to start node and not pointer to pointer to start node .

Thanks

Answer 1

Yes. It is possible to delete the last node of a singly linked list, starting from the first node.

Try the following code,

int delete(struct node *head)
{
  struct node *temp =head;
  struct node *t;
  while(temp->next != NULL)
  {
    t=temp;
    temp=temp->next;
  }
  free(t->next);
  t->next=NULL; 
}  

But if there is just a single element in your linked list, then after deleting that element your head pointer will still point to the now deleted memory location in the function from which you called the delete(). In such a case use the following version of delete().

struct node *delete(struct node *head)
{
  struct node *temp =head;
  struct node *t;
  if(head->next==NULL)
  {
    free(head);
    head=NULL;
  }
  else
  {
     while(temp->next != NULL)
     {
        t=temp;
        temp=temp->next;
     }
     free(t->next);
     t->next=NULL; 
  }    
  return head;
}

Call the function delete() as follows,

head=delete(head);

Answer 2

The answer depends on what exactly is meant by the question.

You can, of course, easily and safely delete the last element (= tail element of the list), if the list contains more than one element. Simply iterate to the element before the last, delete the last and update the next pointer in new last element. Note that in that case the caller's head pointer will remain a perfectly valid pointer to a valid list.

However, if the list initially contained only one element (meaning that head is already pointing to the last element) then, of course, you can still easily delete it, but unfortunately you can't update caller's head pointer from inside delete function. After such deletion the caller's head pointer will become invalid. It will point to now-deallocated memory, i.e. it will become a dangling pointer.

Typically, when one implements a function like that, one should make sure that the caller will know when the list becomes empty. It can be implemented in different ways. For example, the caller's head pointer can be made accessible and modifiable from inside the delete function if the first parameter is declared as a pointer-to-pointer to head node

int delete(struct node **phead, int item)
...
delete(&head, 42);

Alternatively delete function can be made to always return the updated head pointer value

struct node *delete(struct node *head, int item);
...
head = delete(head, 42);

I don't know whether that issue point is important in your case. The fact that you mention that head "is not pointer-to-pointer" suggests that this might indeed be important.

P.S. I suspect that the word "last" in your question does not refer to the tail element of the list, but rather refers to the last remaining element of the list. I.e. the question is specifically about the situation when there's only one element left. In that case, see above...