Remove the Nth Node From the End

You are given head, the first node of a singly linked list, and a number n.

Remove the node that is n-th from the end of the list, and return the first node of the changed list. Counting from the end starts at 1: n = 1 is the last node, n = 2 is the node before it, and so on.

Note

• n is always between 1 and the length of the list.
• If n equals the length, the first node is removed, so the first node of the answer is the old second node.
• If the list has one node, the answer is empty: return null (None in Python).

How the input is shown

A list is written as an array of its values from first node to last node. For example, [3, 6, 9] is the list 3 -> 6 -> 9. Your function gets the first node, not the array, and n as a plain number.

Hint: move a first pointer n nodes ahead. Then move a second pointer and the first pointer together until the first pointer reaches the last node. The second pointer now stops just before the node to remove. A dummy node before head handles the case where the first node is removed. This is one pass over the list.