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

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

---

解题分析及思路：

方法：递归

思路：

本题使用递归的方法来解决。具体思路如下：

1. 创建一个虚拟头节点 root，其 Next 指针指向原链表的头节点 head。这样做的目的是为了方便处理删除头节点的情况。
2. 调用 remove 函数进行递归操作。在 remove 函数中，递归地遍历链表，直到链表末尾。
3. 从链表末尾开始，为每个节点计算其到链表末尾的距离 index。
4. 当 index 等于 n 时，说明当前节点的下一个节点就是要删除的节点，将当前节点的 Next 指针指向下下个节点，从而删除倒数第 n 个节点。
5. 最后返回虚拟头节点的 Next 指针，即删除节点后的链表头节点。

func removeNthFromEnd(head *ListNode, n int) *ListNode {
	var root = &ListNode{Val: -101, Next: head}
	remove(root, n)
	return root.Next
}
func remove(head *ListNode, n int) int {
	if head == nil {
		return 0
	}
	var index = remove(head.Next, n)
	if index == n {
		head.Next = head.Next.Next
	}
	return index + 1
}

复杂度：

• 时间复杂度：O(L)，其中 L 是链表的长度。递归函数需要遍历链表一次，因此时间复杂度为 O(L)。
• 空间复杂度：O(L)，主要是递归调用栈的空间开销，递归的深度最大为链表的长度 L。

执行结果：

• 执行耗时:0 ms,击败了100.00% 的Go用户
• 内存消耗:3.8 MB,击败了12.19% 的Go用户