头结点（2021-09-17:给你一个链表）

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代码](https://github.com/algorithmzuo/coding-for-great-offer/blob/main/src/class28/Problem_0019_RemoveNthNodeFromEndofList.java)