删除链表的倒数第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]
思路
题目要求
- 题目给定一个单链表，要求删除倒数第
n个节点 - 返回删除后的链表的头节点
暴力解法：遍历一遍链表，获知链表的总长度L，第二遍遍历删除从开头数起第(L-n+1)个节点。时间复杂度为O(2n)。
模式识别：
- 设计链表的特殊位置，考虑快慢指针
- 要删除链表节点，找到它的前驱节点
双指针法：先让快指针走n步，此时快慢指针之间距离为n。然后快慢指针同时移动，当快指针移动到 nil时，慢指针指向的节点的后一个节点就是要删除的倒数第n个节点。一遍遍历，时间复杂度为O(n)。
注意
- 使用虚拟头结点，这样方面处理删除实际头结点的逻辑
- 定义fast指针和slow指针，初始值为虚拟头结点
- 返回
dummyNode+1，因为head可能会被删除
代码
Go
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func removeNthFromEnd(head *ListNode, n int) *ListNode { dummyNode := new(ListNode) dummyNode.Next = head slowIndex, fastIndex := dummyNode, dummyNode for i := 0; fastIndex != nil; fastIndex = fastIndex.Next { if i > n { slowIndex = slowIndex.Next } i++ } slowIndex.Next = slowIndex.Next.Next return dummyNode.Next }
