65 votes 65 votes Let $P$ be a singly linked list. Let $Q$ be the pointer to an intermediate node $x$ in the list. What is the worst-case time complexity of the best-known algorithm to delete the node $x$ from the list ? $O(n)$ $O(\log^2 n)$ $O(\log n)$ $O(1)$ DS gateit-2004 data-structures linked-list normal ambiguous + – Ishrat Jahan asked Nov 1, 2014 edited Jan 5, 2018 by kenzou Ishrat Jahan 24.6k views answer comment Share Follow See all 20 Comments See all 20 20 Comments reply Show 17 previous comments Kiyoshi commented Sep 11, 2021 reply Follow Share Question : “Let P be a singly linked list. Let Q be the pointer to an intermediate node x in the list. What is the worst-case time complexity of the best-known algorithm to delete the node x from the list ?” Any node in the linked list have two things first is value and second is address. Question specifically mentions about Q be a pointer that means it contain address. So, node x must represent a node with value x and finally O(1) is the answer for sure. 0 votes 0 votes Shatakshi_1 commented Aug 16, 2023 reply Follow Share i think the answer should be option C. the question says Q pointer points to intermediate node which means middle node right? so to delete that node we will have to traverse till one node before Q so Q → next can be stored in the next of previous node of Q. So shouldn’t it be O(logn)? Please help @Arjun 0 votes 0 votes ꧁༒☬ĿọŗԀ 🆂🅷🅸🆅🅰☬༒꧂ commented Nov 28, 2023 reply Follow Share @Shatakshi_1 first thing here intermediate node doesn’t necessarily means only middle node . It can be anything except the first and last node ig . and second thing to Find the middle node of the Linked list still takes $O(n/2)$ time where we use slow Fast Pointer in which we increase fast pointer by $2$ and slow pointer by one node then fast pointer points to the last node or null (depends on the number of nodes in the linked list ) slow points to the middle of the list so using iterative method still it will take $O(n/2)$ time i hope it will clear ur doubt :) 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes bcoz of says intermediate node means ; if total n element , then we go to intermediate through (n/2) ; and it already says worst case ; means O(n); may be this approach is right ; vcrname9295 answered Dec 4, 2018 vcrname9295 comment Share Follow See 1 comment See all 1 1 comment reply Nandkishor3939 commented Sep 27, 2019 reply Follow Share lol 0 votes 0 votes Please log in or register to add a comment.