在某些语言中，由于需要自行对内存进行管理。因此在实际的面试中，对于「是否需要释放被删除节点对应的空间」这一问题，我们需要和面试官进行积极的沟通以达成一致。下面的代码中默认不释放空间。

已知头结点head和第n个节点，求如何找到倒数第n个节点并删除它，返回头结点。
首先最先想到的是，先遍历一遍链表，得到链表的长度，记为length；再次遍历链表，当遍历到位置L -n + 1时，这个节点的下一个节点就是要删除的节点。这个节点是待删除节点的前驱节点。这样再修改一次指针，就完成了删除操作。

为了方便起见，我们将链表的头节点编号为1。
一般操作链表，都设置一个哑结点dummy，防止出现跨越边界的情况。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
 class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        int length = getLength(head);
        ListNode curr = dummy;
        for (int i=1; i<length -n + 1; ++i) {
            curr = curr.next;
        }
        curr.next = curr.next.next;
        return dummy.next;
    }
    public int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            ++length;
            head = head.next;
        }
        return length;
    }
}

思路二：链表入栈。先进先出。在要把n节点入栈之前，n节点就是要删除的节点，上一个已经入栈的节点，就是待删除节点的前驱结点。

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head);
    Deque<ListNode> stack = new LinkedList<ListNode>();
    ListNode curr = dummy;
    while (curr != null) {
        stack.push(curr);
        curr = curr.next;
    }
    for(int i=0; i<n; ++i) {
        stack.pop();//把后来的，大于等于n的节点都弹出去，弹到哪了不知道
    }
    ListNode prev = stack.peek();
    prev.next = prev.next.next;
    return dummy.next;
}