19. 删除链表的倒数第N个节点

解题思路
思路：找到要删除节点的前一个节点的位置，pre.next = pre.next.next删除即可
1.考虑到如果要删除头节点的特殊性，所以要增加哨兵节点
2.通过遍历整个链表来统计链表的长度length，再通过n与length的关系定位到前一节点
代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
    
        #创建哨兵节点(用来处理删除头节点的情况)
        S_node = ListNode(0)
        #指向头节点
        S_node.next = head
        pre = S_node
        length = 0 #计算链表的长度
        
        #计算链表的长度
        while head!=None:
            length += 1
            head = head.next
        #找到要删除节点的前一节点位置（此处考虑到哨兵节点的情况）
        size = length-n
        for i in range(size):
            pre = pre.next
        #删除节点
        pre.next = pre.next.next
        return S_node.next

方法二: 使用双指针

由于头节点有可能被删除,故设置 pre 指针指向 head
设置快慢指针 前后指针 start, end, 指向 pre. 先让 end 走 n 步, 再将 start 和 end 一起移动.当 end.next 为 None时, 也就是 end 到了尾节点时, start 真好走到待删除节点的前一个节点.
此时 让 start.next = start.next.next, 即可删除 倒数第 n 个节点. 返回 pre.next 即可. 此处不返回 head 是因为 head 可能被删除.

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
       
        pre = ListNode(0)
        pre.next = head
        start = pre
        end = pre

        count = 0
        while count<n:
            start = start.next
            count += 1
        while start.next != None:
            start = start.next
            end = end.next
            
        end.next = end.next.next
        return pre.next