19 Remove Nth Node From End of List
Given a linked list, remove the nth node from the end of list and return its head.
For example,
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Try to do this in one pass.
@tag-linkedlist

Algorithm

The problem requires a single traversal to solve the problem, so you have to think of some more clever ways. For example, the first thing to consider is how to find the Nth node from the bottom. Since only one traversal is allowed, a complete traversal cannot be used to count the number of elements in the linked list. Instead, it should be removed after traversing to the corresponding position.

So you need to use two pointers to help solve the problem, pre and cur pointers. First, the cur pointer moves forward by N steps. If cur points to empty at this time, indicating that N is the length of the linked list, the first element that needs to be removed is the first element. Then return head->next at this time. If cur exists, continue to Go down, at this time the pre pointer also follows, until cur is the last element and stop, at this time pre points to the previous element of the element to be removed, and then modify the pointer to skip the element to be removed