You are given the head of a singly linked list and a number n. Delete the node that sits n-th from the end of the list and return the head of what is left. Counting from the end, the last node is the 1st, the one before it is the 2nd, and so on.
Counting back from the end, 3 is 1st, 7 is 2nd, 1 is 3rd and 9 is 4th, so 9 goes and 4 now links straight to 1.
The 3rd node from the end of a 3-node list is the head itself, so the list now starts at 2.
Removing the only node leaves an empty list.
Constraints
sz nodes, with 1 <= sz <= 30.0 <= Node.val <= 1001 <= n <= szIf one pointer starts n nodes ahead of another and both then move one node at a time, the trailing pointer stays exactly n nodes behind. When the leading one reaches the end, the trailing one is right where the deletion happens.
To remove a node from a singly linked list, you need the node before it, so you can point that node past it. The trouble is that "n-th from the end" counts from the side you can't start at. You can only walk forward from head, and you don't know where the end is until you hit it.
Time O(sz)Space O(1)
The full walkthrough and code are part of Premium