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

题目

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例

输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]

解题思路

对于单链表的删除操作，如果想要做删除链表的倒数第n个结点，则需要找到倒数第n+1个结点的位置。而由于链表只能单向访问，因此，处理这个问题的基本方法是双指针。

令指针p1先遍历n+1步，然后，指针p2再开始与p1同时遍历，直到p1指向nil为止，然后删除p2.Next就可以了。

然而这里有一种特殊情况，就是删除的结点为头节点，此时链表的头节点会改变。为了处理这个问题，有两种办法：

1. 判断被删除的结点是否是头节点，如果是头节点，则修改返回结果
2. 添加一个桩结点，结果返回桩结点的Next指针。

事实证明，方法2是更简单的，也是更通用的。

最后给出我们的实现代码：

type ListNode struct {
	Val  int
	Next *ListNode
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
	if head == nil {
		return nil
	}
	vNode := ListNode{Next: head}
	h1 := &vNode
	h2 := &vNode
	// 第一个指针向前遍历n+1个位置
	for i := 0; i < n+1; i++ {
		if h1 == nil {
			return nil
		}
		h1 = h1.Next
	}
	// 然后双指针同时遍历
	for h1 != nil {
		h1 = h1.Next
		h2 = h2.Next
	}
	// 删除第n个结点
	h2.Next = h2.Next.Next
	// 返回结果
	return vNode.Next
}