删除链表的倒数第N个节点，剑指offerII（21）,力扣

1、创建亚节点 dummy（充当虚头结点）,指向 head

2、创建双指针,fast,s low,这里指针 fast 直接指向 head，而指针 s low 需要指向被删除节点的上一个节点（不然被删节点后面节点也跟着被删了），因此需要初始化指向dummy节点

3、循环遍历，fast 指针先走n步，然后fast与s low 同步移动（此时二者相差n-1个节点），最后直到fast指向null，那么此时s low指向的是被删节点的前驱节点

4、最后返回链表，不过要注意是返回 dummy.next即链表的第一个节点，如果返回 head在特殊情况下会报错。

代码 实现：

/**
 * 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; }
 * }
 */
 
 //这里first即fast，second即slow
          
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head); //创建亚节点
        ListNode first = head;
        ListNode second = dummy;
        for (int i = 0; i < n; ++i) {
            first = first.next;        //指针fast 先走n步
        }
        while (first != null) {
            first = first.next;
            second = second.next;     //fast 与slow同步移动，直至 fast指向null
        }
       //被删节点的上一节点的next指向被删节点的下一节点，即删除节点操作
        second.next = second.next.next;
        ListNode ans = dummy.next;
        return ans;//这里如果返回head的话，那么当链表只有一个元素并且删除一个元素的时候返回的不是空
    }
}

代码 说明：

解题思路里讲的特殊情况，即链表只有一个元素时要删除这个元素，则会报错，所以保险起见，还是用设置头指针指向链表第一个结点的方式比较稳妥。

代码 实现（计算链表长度）：

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        int length = getLength(head);
        ListNode cur = dummy;
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        ListNode ans = dummy.next;
        return ans;
    }

    public int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            ++length;
            head = head.next;
        }
        return length;
    }
}

代码 实现（栈）：

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        Deque<ListNode&gt; stack = new LinkedList<ListNode&gt;();
        ListNode cur = dummy;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        for (int i = 0; i < n; ++i) {
            stack.pop();
        }
        ListNode prev = stack.peek();
        prev.next = prev.next.next;
        ListNode ans = dummy.next;
        return ans;
    }
}