力扣链表基础之删除链表的倒数第N个节点

发表于

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

示例

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

思路

使用虚拟头节点。

如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。

实际操作中可以让fast先移动n+1步，然后让fast和slow同时移动，直到fast指向NULL，此时slow恰好指向待删除结点的上一个，此时执行删除结点的操作即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// fast先移动n+1步，然后让fast和slow同时移动
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	dummy := new(ListNode)
	dummy.Next = head
	fast := dummy
	for i := 0; i < n+1; i++ {
		fast = fast.Next
	}
	slow := dummy
	for fast != nil {
		fast = fast.Next
		slow = slow.Next
	}
	if slow != nil && slow.Next != nil {
		slow.Next = slow.Next.Next
	}
	return dummy.Next
}