Let X is representing Which has to be delete Node
in a single linked list, We have only next pointer but not a previous pointer.
But we have find the previous node to X ==> which takes O(n) in worst case, After finding it,
Prev -> next = q-> next ;
free(q) ;
which takes O(1) time only.
TC = O(n) + O(1) = O(n).
Note that, Algorithm should work in all cases