There is a singly linked list. We have a pointer to a particular node(it is not tail node). what is the time and space complexity required to delete this node?
my approach is... As there is no previous pointer so we traverse the list from the starting to just before the concerned node. then we adjust the pointers like this
let ptr be a pointer pointing to the node to be deleted
while(temp->next!=ptr)
{
temp=temp->next; //temp will point to the node left to ptr
}
temp->next=ptr->next;
free(ptr);
if the node to be deleted is the second last node then we have to traverse the list upto 3rd element from the last node. so I'm getting time complexity as O(n) and space complexity O(1).
but in the book the time complexity is mentioned O(1)
where am I going wrong?