题目描述

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

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

思路

设置快慢指针，快指针先走2步，慢指针再同步遍历
快指针为空，进行删除。

class ListNode:
    def __init__(self, val=0):
        self.next = None
        self.val = val
class Solution:
    def removeNthFromEnd(self, head, n):
        if not head:
            return None
        dummy = ListNode(0)
        dummy.next = head
        fast = dummy
        slow = dummy
        # 走n+1步
        while n >= 0:
            fast = fast.next
            n -= 1
        # 当fast为空退出
        while fast:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return dummy.next