سوال ۶۳ کنکور ارشد علوم کامپیوتر ۱۴۰۵

Setting up the problem

We have a singly-linked list with head pointer $P$ and a pointer $Q$ to the middle node $X$. We must delete the node object that $Q$ points to.

Why the predecessor is required

To unlink a node from a singly-linked list you have to redirect the predecessor's next pointer past it:

$\text{pred}\to\text{next} := Q\to\text{next}$

But a singly-linked node stores no back-pointer, so the only way to find $Q$'s predecessor is to walk from the head $P$ until you reach the node whose next equals $Q$. Since $Q$ is the middle node this scan touches about $n/2$ nodes, i.e. $\Theta(n)$, and no known method beats it — so the cost is $O(n)$.

The famous $O(1)$ trick does not solve this task

There is a well-known constant-time trick for a non-tail node:

Q.data = Q.next.data
Q.next = Q.next.next   // frees the successor node

This runs in $O(1)$, but look at which node it removes: it deletes $Q$'s successor, while node $Q$ survives holding a copied value. The problem asks to delete node $Q$ itself, so the trick answers a different question. To remove the actual node $Q$ you are forced back to locating its predecessor, which is $O(n)$.

Hence the best known algorithm is $O(n)$ — option 2.

Pitfall: The copy-and-delete trick is $O(1)$ only for deleting the value at $Q$ (and only when $Q$ is not the tail). It does not remove the node object $Q$; deleting that specific node needs its predecessor, which is $O(n)$ in a singly-linked list.