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

题解

本题在一次遍历中找到了链表的倒数第 k 个元素，这种思想非常巧妙。
要删除倒数第 n 个节点，就要获得倒数第 n+1 个节点的引用。
获取单链表的倒数第 k 个节点，就是想考察双指针技巧中快慢指针的运用，一般都会要求 只遍历一次链表，就算出倒数第 k 个节点。
第一步，我们先让一个指针 p1 指向链表的头节点 head，然后走 k 步；

第二步，用一个指针 p2 指向链表头节点 head；

第三步，让 p1 和 p2 同时向前走，p1 走到链表末尾的空指针时走了 n-k 步，p2 也走了 n-k 步，也就是链表的倒数第 k 个节点。

这样，只遍历一次链表，就获得了倒数第 k 个节点 p2。

代码实现中在链表头部接一个虚拟头节点 dummy 是为了避免删除倒数第一个元素时出现空指针一场，在头部加入 dummy 节点并不影响尾部倒数第 k 个节点元素是什么。

代码实现

// 使用快慢指针（含虚拟头节点）
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	dummy := &ListNode{Val: -1}
	dummy.Next = head
	// 找到倒数第 n+1个节点
	x := findFromEnd(dummy, n+1)
	// 删除下一个节点
	x.Next = x.Next.Next
	return dummy.Next
}

// findFromEnd 查找倒数第 k 个节点
func findFromEnd(dummy *ListNode, k int) *ListNode {
	p1 := dummy
	for i := 0; i < k; i++ { // 快指针 p1 先走 k 步
		p1 = p1.Next
	}
	p2 := dummy
	for p1 != nil { // 慢指针 p2 走了 length(list) - k 步
		p1 = p1.Next
		p2 = p2.Next
	}
	// 此时 p2 指向要删除节点上一个节点
	return p2
}