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

·题目描述

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

 

示例 1：


输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：

输入：head = [1], n = 1
输出：[]
示例 3：

输入：head = [1,2], n = 1
输出：[1]

·解题思路

利用快慢指针，慢指针比快指针晚出发n步。当快指针到达链表的末尾时候，慢指针正好到达要删除的元素的前一个结点，然后删除下位置结点即可。

————注意点————

1.当n不为0时，快指针不断往后移动

2.当n==0 时候，慢指针的位置为头结点的位置

3.当移除结点为头结点，判断条件 fast is None and  slow is head，此时只需要返回head.next即可

4.当移除元素为中间结点的时候。fast和slow 不断往后移动，直到fast到达末尾，

slow.next = slow.next.next

5.当移除结点为尾结点时，判断条件fast.next is None and slow.next is fast，此时只需要把slow.next指向None 即可。

·代码

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution(object):

    def removeNthFromEnd(self, head, n):
        fast = head

        if fast.next is None and n == 1:
            return None

        while n > 0:
            fast = fast.next
            n -= 1

        ##处理头节点
        if fast is None:
            head = head.next
            return head


        slow = head
        while fast.next :
            fast = fast.next
            slow = slow.next

        slow.next = slow.next.next

        return head

        ##处理尾节点
        if fast.next is None and slow.next == fast:
            slow.next = None
            return head