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

 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]

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

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

思路：双指针，这里解释一下为什么要在head前创建一个新的节点dummy，这样做可以避免讨论头结点被删除的情况，不管原来的head有没有被删除，直接返回dummy.next即可

时间复杂度：O(N)

空间复杂度：O(1)

/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/// 这里解释一下为什么要在head前创建一个新的节点，这样做可以避免讨论头结点被删除的情况，不管原来的head有没有被删除，直接返回dummy.next即可funcremoveNthFromEnd(head*ListNode, nint) *ListNode {
ifhead==nil {
returnnil    }
dummy :=&ListNode{0, head}
fast, slow :=dummy, dummyfori :=0; i<n&&fast!=nil; i++ {
fast=fast.Next    }
forfast!=nil&&fast.Next!=nil {
fast=fast.Nextslow=slow.Next    }
slow.Next=slow.Next.Nextreturndummy.Next}