题目

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

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

• 给定的 n 保证是有效的。

进阶：

尝试使用一趟扫描实现？

方案一

• 最先想到的算法，步骤如下
  1. 循环一遍链表找到链表的长度
  2. 再次循环，并删除指定的节点
• 如果删除的是头结点，直接返回第二个节点即可

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    if head == nil {
        return head
    }

    length := 0
    node := head
    for node != nil {
        length += 1
        node = node.Next
    }
    index := length - n
    if index == 0 {
        return head.Next
    }

    // 删除指定位置节点
    prev := head
    node = head.Next
    for i := 0; i < index - 1; i++ {
        prev = node
        node = node.Next
    }
    prev.Next = node.Next
    return head
}

• 时间复杂度

方案二

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    if head == nil {
        return nil
    }

    l := make([]*ListNode, 0)
    node := head
    for node != nil {
        l = append(l, node)
        node = node.Next
    }
    if n > len(l) {
        return nil
    }
    if n == len(l) {
        return head.Next
    }

    prev := l[len(l) - n - 1]
    nNode := l[len(l) - n]
    prev.Next = nNode.Next
    return head
}

• 遍历的同时将各个节点指针保存好即可

方案三（双指针技巧）

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    var dummyHead = &ListNode{0, head}
    var firPtr = dummyHead
    var secPtr = dummyHead
    var size = 1
    for ; firPtr.Next != nil; size++ {
        firPtr = firPtr.Next
        if size > n {
            secPtr = secPtr.Next
        }
    }
    secPtr.Next = secPtr.Next.Next
    return dummyHead.Next
}

• 保证两个指针之间的窗口大小为N，则当第一个指针遍历到链表尾部时，第二个指针则指向的是倒数第N个节点。

双指针技巧解析：

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-by-l/

原文

https://leetcode-cn.com/explore/learn/card/linked-list/194/two-pointer-technique/747/