题目描述#

给你一个链表的头节点 head，要求删除链表的倒数第 n 个节点，并返回删除后的链表头节点。

这道题的关键不在于找到节点的值，而在于真正把目标节点从链表里摘掉，所以最后需要调整前后节点的指针连接关系。

思路#

这份代码使用的是链表里很经典的双指针做法。先创建一个哑节点 dummy 指向原链表头部，这样即使要删除的是原来的第一个节点，也可以统一按“删除某个节点的前一个节点后面那个节点”的方式处理，不需要单独分类讨论。

接下来让 slow 和 fast 都从 dummy 出发，但先让 fast 多走 n+1 步。这样做之后，fast 和 slow 之间就始终隔着 n 个节点。后面再让两个指针一起往后走，直到 fast 走到 nil，此时 slow 正好停在“倒数第 n 个节点”的前一个位置。

既然 slow 已经来到了目标节点的前驱，那么删除操作就很直接了，只需要执行 slow.Next = slow.Next.Next，把目标节点从链表中跳过去即可。

整个过程只遍历链表一次，时间复杂度是 O(n)，额外只用了几个指针变量，空间复杂度是 O(1)。

代码#

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	dummy := &ListNode{Next: head}
	slow := dummy
	fast := dummy
	// 让fast指针先走n+1步
	for i := 0; i <= n; i++ {
		fast = fast.Next
	}
	for fast != nil {
		fast = fast.Next
		slow = slow.Next
	}
	slow.Next = slow.Next.Next
	return dummy.Next
}