Leetcode 19: remove Nth node from end of list

Given a linked list, remove the n^th 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. 

这一题要求one pass， 首先想到是利用空间换时间，用一个map来记录node的位置和node pointer,

这种方法是可行的，但是空间复杂度为O（n），有没有O（1）的方法呢？？后来是在网上看到有人做的

方法，是用slow 和 fast指针，首先将slow 和fast指针移动使其之间间隔的node是n，然后将fast移动

到链表尾部，此时slow就是需要删除的节点了。

很多题目中都用到了slow 和fast指针的思想，比如： quick sort 和对一个array中的element进行

shuffle对素按照一定规则移动，或者string里面对char的一些操作，通过swap slow 和fast的元素实现， 此时的slow 和 fast相等两个

挡板，slow 和fast指针同向或者反向走；还有在linklist中，one pass求linklist的middle point,求linklist里面是否有circle，求

linklist里面的circle点， slow 走慢一些，fast走快一些，或者将fast定在一个位置，再将fast和slow同步走，

在这题中，就是后面的那个思想，要删除链表后面的第N个元素，slow 和fast指针之间相差N个节点，可以先将fast

移动到第N个节点处，然后slow和fast同步走，当fast走到了表尾，说明slow此时到达了要删除的节点位置，用

pre指针删除即可。

class Solution {
public:
//use a slow and fast pointer
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        //sanity check
        if (head == NULL) return NULL;
        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        for (int i = 0; i < n-1; i++) {
            fast = fast->next;
        }
        ListNode* pre = dummy;
        while (fast && fast->next) {
            fast = fast->next;
            pre = slow;
            slow = slow->next;
        }
        pre->next = slow->next;
        return dummy->next;
        delete dummy;
    }
};
time complexity: O(n)
space complexity: O(1)