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.
这里的Note的意思应该就是可以不做特殊处理n值了。不过其实特殊处理也就一句语句。
思路：
快指针和慢指针的概念，先一个指针先走，到了离起点n个节点远的时候，慢指针走，等到快指针走到结尾，那么慢指针走到了需要删除的位置了。
初学者注意：保留慢指针的前置指针，这样才能删除。
注意：特殊处理需要删除头指针的情况，如输入1->2->3->4; n=4，那么需要删除1，这就需要特殊处理了，头指针往前一步就可以了。
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *removeNthFromEnd(ListNode *head, int n)
{
ListNode *end = head;
int i = 0;
for (; i < n; i++)
{
if (end) end = end->
next;
else break;
}
if (i != n) return head;
findDeletePos(head, head, head, end);
return head;
}
void findDeletePos(ListNode *(&head), ListNode *pre, ListNode *cur, ListNode *end)
{
while (end)
{
end = end->next;
pre = cur;
cur = cur->next;
}
//注意：删除头指针的时候要做特殊处理
if (pre == cur)
{
head = head->next;
return;
}
pre->next = cur->next;
}
};