2021-09-17：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。进阶：你能尝试使用一趟扫描实现吗

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代码