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 Q from the list?
- A.O(n)
- B.O(log2 n)
- C.O(logn)
- D.O(1)
Show answer
Answer: D. O(1)
Copying data from the succeeding node into Q and bypassing the succeeding node allows deletion in O(1) time.