一、题目

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

二、解法

思路：双指针p1、p2。p1从head开始往后遍历，p2从第n+1个节点开始往后遍历，当p2到达倒数第一个节点的时候，p1则到达了倒数n+1个节点。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
 // 思路
 // 双指针
 // head开始遍历
 // p2 比 p1 提前n
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    if n== 0 {
        return head
    }

    p1 := head
    p2 := head
    for n > 0 {
        p2 = p2.Next
        n --
    }

    // 代表删除第一个节点
    if p2 == nil {
        head = head.Next
        return head
    }

    // p1和p2 每次都是往后移动，当p2为null的时候，即p1在倒数第n个节点
    for p2.Next != nil {
        p1 = p1.Next
        p2 = p2.Next
    }

    // 删除倒数第n个节点
    p1.Next = p1.Next.Next

    return head
}