题目描述
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
截屏2022-03-27 下午8.54.46.png
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1
输出：[]
题解
思路1:计算链表长度
先获取链表的长度L。随后再从头节点开始对链表进行一次遍历，当遍历到第L−n+1 个节点时，它就是我们需要删除的节点。
static public func removeNthFromEnd1(_ head: ListNode?, _ n: Int) -> ListNode? {
let dump = ListNode(0,head)
var first = head
var len = 0
while first != nil {
first = first?.next
len += 1
}
var second = dump
for _ in 1..<(len-n+1) {
second = second.next!
}
second.next = second.next?.next
return dump.next
}
思路2:双指针
由于我们需要找到倒数第n个节点，因此我们可以使用两个指针first 和second同时对链表进行遍历，并且first比second超前n个节点。当first 遍历到链表的末尾时，second 就恰好处于倒数第n 个节点。
具体地，初始时first和second均指向头节点。我们首先使用first对链表进行遍历，遍历的次数为n。此时，first和second之间间隔了n−1个节点，即first 比second 超前了n 个节点。在这之后，我们同时使用first 和second对链表进行遍历。当first遍历到链表的末尾（即first 为空指针）时，second 恰好指向倒数第n 个节点。
根据方法一，如果我们能够得到的是倒数第n 个节点的前驱节点而不是倒数第n 个节点的话，删除操作会更加方便。因此我们可以考虑在初始时将second 指向哑节点，其余的操作步骤不变。这样一来，当first 遍历到链表的末尾时,second 的下一个节点就是我们需要删除的节点。
static public func removeNthFromEnd2(_ head: ListNode?, _ n: Int) -> ListNode? {
let dump = ListNode(0,head)
var first = head
for _ in 0..<n {
first = first?.next
}
var second = dump
while first != nil {
first = first?.next
second = second.next!
}
second.next = second.next?.next
return dump.next
}
思路3:使用额外空间
先使用数组存储各个节点，然后再删除第L-n节点，再将数组中的节点按顺序组织起来
static public func removeNthFromEnd3(_ head: ListNode?, _ n: Int) -> ListNode? {
var list:[ListNode] = [ListNode]()
var cur = head
while cur != nil {
list.append(cur!)
cur = cur?.next
}
let count = list.count
if n > count {
return head
}
list.remove(at: count-n)
let root = ListNode(-1)
var tempNode = root
for i in 0..<list.count {
tempNode.next = list[I]
tempNode = tempNode.next!
tempNode.next = nil
}
return root.next
}
参考：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
