一. 题目

二. 思路

1. 两次遍历

• 第一次遍历计算链表长度。

• 第二次遍历找到删除的点。

2. 栈

• 先将所有节点入栈。

• 然后将所有出栈，出栈的第N个节点即为要删除的节点。

3. 双指针

4. 哈希

• 遍历一次链表，在遍历的过程中哈希存储第几个节点到节点的映射，然后计算出要删除的节点是第几个即可。

三. 代码

3. 双指针

class Solution
{
    final ListNode h = new ListNode();

    public ListNode removeNthFromEnd(ListNode head, int n)
    {
        h.next = head;
        ListNode pre = h, ne = head;
        for (int i = 0; i < n; ++i)//先让ne走n步
            ne = ne.next;

        while (ne != null)//同时走
        {
            pre = pre.next;
            ne = ne.next;
        }
        pre.next = pre.next.next;//删除节点
        return h.next;
    }
}

4. 哈希

class Solution
{
    final Map<Integer, ListNode> map = new HashMap<>();
    final ListNode h = new ListNode();

    public ListNode removeNthFromEnd(ListNode head, int n)
    {
        map.clear();
        int cnt = 0;
        h.next = head;

        map.put(0, h);
        while (head != null)
        {
            map.put(++cnt, head);
            head = head.next;
        }

        ListNode pre = map.get(cnt - n);
        pre.next = pre.next.next;
        return h.next;
    }
}