Given a linked list, remove the n-th node from the end of list and return its head.
Note: Given n will always be valid.
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.
length of link list, remove the
n-th node will be easy if we find the node at pos
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!
Preparing for an interview? Check out this!