学步园

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.

        一次遍历，得到结果，需要保存两个指针，这两个指针所指节点之间的距离是n，这样当后面的指针指向链表尾的时候，前面的指针所指的节点即为要删除的节点。考虑到删除当前节点需要记录当前的前驱节点，我们保存两个指针pre、tail分别指向删除节点的前驱节点和链表尾节点，此时n=n+1，如果tail==NULL是，删除pre->next的节点。

class Solution {
public:
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        if(head==NULL||n<=0)return head;
        ListNode *pre=head,*tail=head;
        n++;
        while(n&&tail){
            tail=tail->next;
            n--;
        }
        if(n>1)return head;
        else if(n==1)return head->next;
        else{
            while(tail){
                pre=pre->next;
                tail=tail->next;
            }
            pre->next=pre->next->next;
        }
        return head;
    }
};