方法一：数组

    1. # 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。 
    2. # 
    3. #  示例： 
    4. # 
    5. #  给定一个链表: 1->2->3->4->5, 和 n = 2.
    6. # 
    7. # 当删除了倒数第二个节点后，链表变为 1->2->3->5.
    8. #  
    9. # 
    10. #  说明： 
    11. # 
    12. #  给定的 n 保证是有效的。 
    13. # 
    14. #  进阶： 
    15. # 
    16. #  你能尝试使用一趟扫描实现吗？ 
    17. #  Related Topics 链表 双指针 
    18. #  👍 1169 👎 0
    21. # leetcode submit region begin(Prohibit modification and deletion)
    22. # Definition for singly-linked list.
    23. class ListNode(object):
    24.     def __init__(self, val=0, next=None):
    25.         self.val = val
    26.         self.next = next
    27. class Solution(object):
    28.     def removeNthFromEnd(self, head, n):
    29.         """
    30.         :type head: ListNode
    31.         :type n: int
    32.         :rtype: ListNode
    33.         """
    34.         curr = head
    35.         cache = []
    36.         while curr:
    37.             cache.append(curr)
    38.             curr = curr.next
    39.         currIndex = n * (-1)
    40.         if n == len(cache):
    41.             head = head.next
    42.         else:
    43.             cache[currIndex - 1].next = cache[currIndex].next
    44.         return head
    46. # leetcode submit region end(Prohibit modification and deletion)

    方法二：快慢指针

    1. class Solution(object):
    2.     def removeNthFromEnd(self, head, n):
    3.         """
    4.         :type head: ListNode
    5.         :type n: int
    6.         :rtype: ListNode
    7.         """
    8.         dummy = ListNode(0, head)
    9.         p1 = head
    10.         p2 = dummy
    11.         for i in range(n):
    12.             p1 = p1.next
    13.         while p1:
    14.             p1 = p1.next
    15.             p2 = p2.next
    16.         p2.next = p2.next.next
    17.         return dummy.next