Leetcode 19 Remove Nth Node From End of List

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？

题意分析：
在原链表中删除倒数第N个节点，让我们只能遍历一遍，如何确定倒数第N个节点的位置是关键！！

思路分析：
这是非常常见的一个思想，对于刚接触算法的人来说可能有点不太容易想到。
那就是使用两个指针，使这两个指针间隔为N，当一个指针指向链表中的最后一个结点时，另一个指针自然就指向了倒数第N个节点。

这里顺带介绍一下链表问题的其他几种常见操作。
找链表的中间位置：
双指针slow,fast，slow每次移动一位，fast每次移动两位，fast到链表结尾时slow自然就在中间。
判断链表是否有环：
双指针slow,fast，slow每次移动一位，fast每次移动两位，当slow和fast相遇则说明链表有环，反之则没有环。

# 24ms, beats 98.88%
class Solution(object):
    def removeNthFromEnd(self, head, n):
        pre, cur = head, head
        for i in range(n): cur = cur.next
        if not cur: return head.next
        while cur.next:
            pre = pre.next
            cur = cur.next
        pre.next = pre.next.next
        return head