Description
Given a linked list, remove the nth node from the end of list and return its head.
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.
Discussion
这个问题要求我们移除掉链表中的倒数第n个元素。常规思路当然是首先遍历一遍链表，得出链表的总长度len，再移除掉第len-n个元素。然而，题目的要求是一次遍历，这就要求我们有更加巧妙的方法。
我们可以设置两个指针preLoc和curLoc，使得两个指针相距为n，且一起往后运动。这样，当后者curLoc运动到链表尾部时，preLoc恰好在倒数第n的位置。
算法的时间复杂度为O(n)。
C++ Code
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode * preLoc = head, * curLoc = head; //设置两个指针相距n，当后面的指针curLoc运动到尾部时，前面的指针就在倒数第n个。
for(int i = 0; i < n; i++)
{
curLoc = curLoc->next;
}
//若恰好有n个元素
if(!curLoc)
{
return head->next;
}
while(curLoc->next)
{
curLoc = curLoc->next;
preLoc = preLoc->next;
}
preLoc->next = preLoc->next->next;
return head;
}
};