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

In a singly linked list, deleting a node requires a pointer to its predecessor, because we can only follow links forward. To remove the second-from-last node we must end up holding a pointer to the third-from-last node (so we can splice past the node being deleted).

The classic single-pass technique uses two pointers separated by a fixed gap. To delete the node that is $k$ from the end, advance a lead pointer $k$ nodes ahead of a trail pointer, then move both together one step at a time. When the lead pointer reaches the last node (or the end), the trail pointer is exactly positioned at the predecessor of the target. Here the target is the $2$nd from the end, so the trail pointer should sit at the $3$rd from the end, i.e. the lead is two nodes ahead of the trail.

... -> [trail] -> [target = 2nd-from-end] -> [last]
                                   ^ lead reaches here
trail.next = trail.next.next   // splice out the target

This runs in a single traversal, $\Theta(n)$ time and $\Theta(1)$ extra space, with no counting of the total length needed.

Why the others are worse:

So the best method is option 4.

Exam trick: For any "$k$-th node from the end" operation on a singly linked list, the standard optimal answer is the two-pointer (fast/slow) technique with the two pointers kept a fixed distance apart — one traversal, constant extra memory.