19_删除链表的倒数第_N_个结点

类型：链表

• 19. 删除链表的倒数第 N 个结点 💛

  https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

  ❓ 给你一个链表，删除链表的倒数第 n 个结点。

  💡 快慢指针

  快指针比慢指针先走 n 步。同时由于可能删除头结点，因此要注意虚拟结点的使用。

  class Solution:
      def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
          if not head:
              return None
          dummyHead = ListNode(next = head)
          fast = dummyHead
          for i in range(n):
              if not fast:
                  return head
              fast = fast.next
          slow = dummyHead
          while fast and fast.next:
              slow = slow.next
              fast = fast.next
          slow.next = slow.next.next
          return dummyHead.next

  时间复杂度：O(n)，空间复杂度：O(1)