"""
Definition of ListNode
class ListNode(object):

    def __init__(self, val, next=None):
        self.val = val
        self.next = next
"""
class Solution:
    """
    @param head: The first node of linked list.
    @param n: An integer.
    @return: The head of linked list.
    """
    def removeNthFromEnd(self, head, n):
        # write your code here
        if head is None: return None
        if n == 0: return head
        cur = head
        follow = head
        pre = head
        for i in range(n):
            follow = follow.next
        # 当follow为null时，此时链表长度等于n，删除第一个元素即可
        if follow is None:
            return cur.next
        # 将pre和fol依次后移，实际后移次数为n-1    
        while follow.next is not None:
            follow = follow.next
            cur = pre
            pre = pre.next
        # 删除第n个元素
        pre.next = pre.next.next
        return head