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]
题解
解法 1：使用 Golang SDK 链表
参考资料：
根据链表分类，题目给到的 ListNode 数据结构属于单向链表，根据单向链表性质，只能从首节点单向向后 next 遍历到尾节点。
根据对双向链表性质的了解，可以知道双向链表支持从尾节点向前遍历 prev 到首节点。
那么题目中的删除链表倒数第 n 个节点，可以转化为从双向链表尾节点开始向前遍历 prev 遍历第 n 个节点。
同时，根据对 Golang SDK 的了解，可以知道 Golang SDK 原生支持双向链表实现，于是可以通过以下步骤实现题目：
- 将
ListNode同步到双向链表list - 从
list尾节点向前遍历n个节点 - 调用
list接口Remove，移除第 2 步中取得的节点 - 将
list同步到ListNode - 返回
ListNode head节点
import "container/list"
func removeNthFromEnd(head *ListNode, n int) *ListNode {
// 通过使用 Golang SDK 新建一个双向链表
l := list.New()
// 将 ListNode 结构复制到链表里面
for head != nil {
l.PushBack(head.Val)
head = head.Next
}
remove := l.Back()
// 从双向链表的末尾向前数 n 个节点就是想要删除的节点
for i := 1; i < n; i++ {
remove = remove.Prev()
}
// 调用 list SDK 接口实现删除逻辑
l.Remove(remove)
// 将双向链表数据重新复制到 ListNode 结构
if l.Len() > 0 {
var newHead, tail *ListNode
element := l.Front()
newHead = &ListNode{Val: element.Value.(int)}
tail = newHead
// 从双向链表的首节点开始遍历
for i := 1; i < l.Len(); i++ {
element = element.Next()
tail.Next = &ListNode{Val: element.Value.(int)}
tail = tail.Next
}
return newHead
} else {
return nil
}
}
解法 2：计算链表的长度
如果我们知道链表的长度 length 的话，我们就可以根据倒数第 n 个节点的信息，推出正数第 m 个节点。
也就是我们遍历到 m=length-n+1 个节点时，它就是我们需要删除的节点。
所以我们可以以下步骤删除倒数：
- 遍历链表获取链表长度
length - 遍历到待删除节点的前一个节点，也就是
cur=length-n个节点 - 将
cur.Next指向cur.Next.Next，即可删除待删除的节点
func removeNthFromEnd(head *ListNode, n int) *ListNode {
length := 0
cur := head
// 遍历 ListNode，获得链表长度 length
for cur != nil {
length++
cur = cur.Next
}
dummy := &ListNode{Val: 0, Next: head}
cur = dummy
// 遍历到待删除节点的前一个节点
for i := 1; i < length-n+1; i++ {
cur = cur.Next
}
// 将待删除的节点的前一个节点的 Next 指向待删除的节点的 Next
// 这样就将待删除节点给删除了
// 例如 a->b-c 链表，
// cur 为 a，
// 将 a.Next 指向 c，
// 也就是 cur.Next = b.next = cur.Next.Next
cur.Next = cur.Next.Next
return dummy.Next
}