给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。(第一个我写的时间太长)
# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution(object):
    def removeNthFromEnd1(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        if not head.next:
            return

        pre = head
        list_data = [head]
        while pre.next:
            list_data.append(pre.next)
            pre = pre.next
        if abs(-n-1) > len(list_data):
            return head.next
        else:
            list_data[-n-1].next = list_data[-n].next
        return head

    def removeNthFromEnd2(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        x = ListNode(100, head)
        m = head
        t = 0
        while m:
            m = m.next
            t += 1
            if t >= n + 1:
                x = x.next
        if t >= n + 1:
            x.next = x.next.next
        else:
            head = head.next
        return head

    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        # if not head.next:
        #     return

        root1 = head
        root2 = head

        for i in range(n + 1):
            if not root1:
                return root2.next
            root1 = root1.next

        while root1:
            root1 = root1.next
            root2 = root2.next
        root2.next = root2.next.next
        return head


if __name__ == '__main__':
    s1 = Solution()
    root = ListNode(1)
    # node1 = ListNode(2)
    # node2 = ListNode(3)
    # node3 = ListNode(4)
    # node4 = ListNode(5)
    #
    # node3.next = node4
    # node2.next = node3
    # node1.next = node2
    # root.next = node1
    print(s1.removeNthFromEnd(root, 1))