学步园

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个节点，显然，获取整个链表的长度然后再从头开始数就不符合要求。看到这道题来自于快慢指针的启发，定义两个指针，第一个指针先走n步，然后两个指针一起走，第一个指针到达最后一个节点，第二个指针到达了要删除的那个节点。这样，代码就比较容易写出了。

class Solution {
public:
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        ListNode* fast = head;
        ListNode* slow = head;
        ListNode* front = head;
        int i = n;
        while(i-- && fast != NULL)
        {
            fast = fast->next;
        }
        if (i >= 0 && fast == NULL)
        {
            return head;
        }
        while(fast != NULL)
        {
            front = slow;
            fast = fast->next;
            slow = slow->next;
        }
        if (front == slow)
        {
            return head->next;
        }
        front->next = slow->next;
        return head;
    }
};