2021-09-17：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。进阶：你能尝试使用一趟扫描实现吗？
福大大 答案2021-09-17：
双指针。
1.创建虚拟头节点preHead，其next节点指向head。
2.右节点先走，遍历n+1个节点。
3.继续遍历，左右节点都指向next。
4.遍历完成后，左节点的next指向左节点的next的next。
5.返回preHead的next节点。
时间复杂度：O(N)。
空间复杂度：O(1)。
代码用golang编写。代码如下：
package main
import (
"fmt"
"strconv"
)
func main() {
head := &ListNode{val: 1}
printlnListNode(head)
ret := removeNthFromEnd(head, 1)
fmt.Println("---------")
printlnListNode(ret)
}
func printlnListNode(head *ListNode) {
for head != nil {
fmt.Print(strconv.Itoa(head.val) + ",")
head = head.next
}
fmt.Println("打印完成")
}
type ListNode struct {
val int
next *ListNode
}
func removeNthFromEnd(head *ListNode, n int) *ListNode {
preHead := &ListNode{val: -1}
preHead.next = head
right := preHead
left := preHead
for i := 0; i < n+1; i++ {
right = right.next
}
for right != nil {
right = right.next
left = left.next
}
left.next = left.next.next
return preHead.next
}
执行结果如下：
左神java代码
