Consider a singly linked list. What is the worst case time complexity of the…

Concept: In a singly linked list, you are normally only given a pointer to the node you want to delete, not to its predecessor — and there is no backward link to fall back on. If that node has a successor, you can copy the successor's stored value into the node and then unlink the successor; this avoids ever needing to reach the predecessor, so it takes a fixed number of steps regardless of list size. But this only works when a successor exists to borrow from — it does nothing to help you locate a predecessor when there is none, and reaching a predecessor directly (with no backward link) can only be done by walking from the head.

Applying this to node a:

1. If a is not the last node, use the successor-copy trick: overwrite a's stored value with the value held in a's successor, then relink a to skip over that successor. This takes a fixed number of steps, whatever the list's length.

2. If a is the last node of the list, it has no successor to copy from, so this trick cannot be applied.

3. In that case, the only way to detach a is to update its predecessor's next pointer — but with only a pointer to a and no backward link available, the predecessor can only be found by starting at the head and following next pointers one at a time until the node just before a is reached.

4. That walk visits nodes in proportion to a's distance from the head, reaching up to all of them when a is the last node — so this position sets the ceiling on how long deletion can take.

Cross-check: The question does not fix where a sits in the list, so the worst case must be taken over every possible position a could occupy — and the last-node position is always a valid one to consider. Since that position forces a full walk from the head, no algorithm can guarantee a bound better than one proportional to list length across all positions of a; the fixed-time case covers only the positions that have a successor, so it cannot be the answer to a worst-case question. This also rules out the other two options: a plain singly linked list has no way to skip toward a target in a halving (logarithmic) number of steps, since every node is reached only by following one next-pointer at a time from the head — there is no shortcut structure and no repeated-halving behaviour anywhere in this operation.

Answer: O(n).