1 votes 1 votes closed as a duplicate of: GATE IT 2004 | Question: 13 Let P be a single linked list.Let Q be a pointer to an intermediate node 'X' in the list.What is the worst case time complexity of best known algorithm to delete the node 'X ' from the list Programming in C linked-list algorithms data-structures + – saipriyab asked Nov 25, 2017 • recategorized Jul 6, 2022 by Lakshman Bhaiya saipriyab 1.4k views comment Share Follow See all 11 Comments See all 11 11 Comments reply Ashwin Kulkarni commented Nov 25, 2017 reply Follow Share is ans O(n) ? 1 votes 1 votes Manu Thakur commented Nov 25, 2017 reply Follow Share O(1) as it's given that it's an intermediate node. 0 votes 0 votes Ashwin Kulkarni commented Nov 25, 2017 reply Follow Share @Manu Thakur Suppose you are given a pointer Q which points to the current node (the one that is to be deleted which is intermediate). Now if we want to delete it then the next address of the previous node must point to the next of the present node. Since it is a singly linked list hence we do not have a pointer to the previous node, in order to obtain that pointer we need to traverse the list. This will take o(n). And intermediate means it can be last but one node also. Correct me if I am wrong 1 votes 1 votes abhishek tiwary commented Nov 25, 2017 reply Follow Share i think pointer is pointing to the element which we have to delete so it will take O(1) 0 votes 0 votes Manu Thakur commented Nov 25, 2017 reply Follow Share @ashwin Suppose we have a linked list as follows A->B->C->D->E and pointer q is given to the node B as B is to be deleted. q.data = q.next.data; q.next = q.next.next; now our modified linked list is A->C->D->E B is removed successfully in O(1) we can do such removal in O(1) except last node deletion. 2 votes 2 votes Ashwin Kulkarni commented Nov 25, 2017 reply Follow Share Ohh I got my mistake. Thankyou so much @Manu Thakur 0 votes 0 votes abhishek tiwary commented Nov 25, 2017 reply Follow Share @ Manu Thakur but by your operation previous node of Q how get connected to Q->next only Q pointer will be point toQ->next 0 votes 0 votes Manu Thakur commented Nov 25, 2017 reply Follow Share @abhishek node is deleted we can set q to null. because job has been done and we don't require it anymore. And B is already connected to A, we don't need to worry about it. we copied data from Node C and connected it to D. 0 votes 0 votes Ashwin Kulkarni commented Nov 25, 2017 reply Follow Share @abhishek Here content of node to which Q is pointing already changed. Hence to need to again point prev of Q to next of Q. 0 votes 0 votes abhishek tiwary commented Nov 25, 2017 reply Follow Share we need another pointer who will point to previous node of Q P->next=Q; then again A will point to C A->C->D... but for this question we do not have to do @ Manu Thakur sir ?? 0 votes 0 votes Manu Thakur commented Nov 25, 2017 reply Follow Share @abhishek why do you need a pointer the the previous node of the node pointedby q? it is written in the question node to be deleted is an intermediate node. if question is to delete the last node then we need a pointer which will point to the second last node. hence to delete last TC is O(n) and other than last node each node can be deleted in O(1) 2 votes 2 votes Please log in or register to add a comment.