Write remove_nth_from_end(head, n): unlink the n-th node counting from the end of the linked list (n = 1 is the last node) and return the head of the resulting list, which may be None.
The list has between 1 and 100,000 nodes, and n is always between 1 and the length of the list. Aim for O(n) time and O(1) extra memory; try to do it in a single pass over the list.
10 -> 20 -> 30 -> 40, n = 2 -> 10 -> 20 -> 40
10 -> 20 -> 30 -> 40, n = 4 -> 20 -> 30 -> 40
10, n = 1 -> (empty)
The remaining nodes must be the original node objects, in the original order.
Show hint
Two pointers that stay a fixed distance apart let you find the node just before the target in one pass. A dummy node in front of the head removes the special case of deleting the first node.