19. 删除链表的倒数第 N 个结点【双指针、栈（Deque类–LinkedList集合：push()、pop()、peek()；）】

19. 删除链表的倒数第 N 个结点

• 图解
  

// 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 {  //java 双指针
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode right = dummy;
        for (int i = 0; i < n; ++i) {
            right = right.next;
        }
        ListNode left = dummy;
        while (right.next != null) {
            right = right.next;
            left = left.next;
        }
        left.next = left.next.next;
        return dummy.next;
    }
}
// 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
// 内存消耗：40 MB, 在所有 Java 提交中击败了5.06%的用户

class Solution {  //java 栈
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        Deque stack = new LinkedList();
        ListNode cur = dummy;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        for (int i = 0; i < n; ++i) {
            stack.pop();
        }
        ListNode pre = stack.peek();
        pre.next = pre.next.next;
        return dummy.next;
    }
}
// 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
// 内存消耗：40 MB, 在所有 Java 提交中击败了5.06%的用户