打卡题目：leetcode第19题，删除链表的倒数第N个节点
    相似题目：82、83、203、237
    image.png

    【思路】

    • 解法一：遍历链表，得到链表长度N。那么删除倒数第n个节点，即为删除第N-n个节点。找到第N-n-1个节点，记为 p, q = p.next, p.next = p.next.next, del p （记得清除内存）。
    • 唯一的问题是：如何删除第1个元素，需要单独判断？可以不用这么麻烦，增加一个无意义的头结点，所有的删除逻辑都变成一致的了！
    • 解法二：使用两个指针first和second遍历链表，首先，first指针前进n步，second指针不变；紧接着，first指针和second指针同时前进，直到first.next为None。此时，second指针指向的是倒数第n+1个节点，second.next = second.next.next 同时删除无用内存即可。（删除第1个元素的代码逻辑与其它元素的不一样，解决方法参考解法一的说明。）

    【代码】

    1. # Definition for singly-linked list.
    2. # class ListNode:
    3. #     def __init__(self, val=0, next=None):
    4. #         self.val = val
    5. #         self.next = next
    6. class Solution:
    7.     def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
    8.         # 增加空的头结点，使得逻辑一致
    9.         node = ListNode(val=0, next=head)
    10.         head = node
    11.         # 找到第n-1个节点
    12.         count = 0
    13.         p = head
    14.         while count < n:
    15.             count += 1
    16.             p = p.next
    17.         # 找到倒数第n+1个节点
    18.         q = head
    19.         while p.next:
    20.             p = p.next
    21.             q = q.next
    22.         # 删除倒数第n个节点
    23.         r = q.next
    24.         q.next = q.next.next
    25.         del r
    26.         return head.next