【力扣】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

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

题解：

双指针法（快慢指针法）：

// 时间复杂度：O(n)
// 空间复杂度：O(1)
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	// 创建哨兵节点(哑节点)
	dummyHead := &ListNode{
		Next: head,
	}
	// 定义一个慢指针和一个快指针
	slow, fast := dummyHead, dummyHead
	i := 0
	for fast != nil {
		// 快指针始终在移动
		fast = fast.Next
		// 快指针比慢指针先走了 n+1 步
		if i >= n+1 {
			// 当快指针比慢指针先走了 n+1 步，再往前走的时候慢指针跟着移动
			slow = slow.Next
		}
		i++
	}
	// 此时的慢指针正好落在了要删除节点的前一位，进行删除操作
	slow.Next = slow.Next.Next
	return dummyHead.Next
}