Description
Given a linked list, remove the nth node from the end of list and return its head.
Example:

Note: Given n will always be valid.
Naive solution
First, we need to get the length
of the link list, the time complexity will be $O(N)$, we can not avoid this step, so this is also the best time complexity.
Given the length
of link list, remove the nth
node will be easy if we find the node at pos lengthn
.
Note a dummy node
will make the code cleaner.

Approach with two pointers
This is a clever approach, if we use two pivot pointers, their distance is n+1
. Then if we move the tail forward to the end of linklist, the prev
will be the pointer whose next can be deleted!

Join my Email List for more insights, It's Free!😋