codejump
MediumPythonJavaScriptTypeScript

Linked List — Remove the Nth Node From the End

Data StructuresLinked ListTwo Pointers

solve(values, n) builds a singly linked list from values, removes the n-th node
counted from the end (n = 1 is the tail), and returns the remaining values. n is
always between 1 and the list length.

Do it in one pass. Put a dummy node before the head (so removing the head needs no
special case), move a fast pointer n steps ahead, then advance fast and slow
together. When fast reaches the last node, slow stands right before the node to remove.

Examples

solve([1,2,3,4,5], 2)  → [1,2,3,5]
solve([1], 1)          → []
solve([1,2], 2)        → [2]       // removing the head

Sample tests

Test #1Second from the end
Input: [[1,2,3,4,5],2]
Output: [1,2,3,5]
Test #2Only node
Input: [[1],1]
Output: []
Test #3Remove the head
Input: [[1,2],2]
Output: [2]