[数据结构与算法]删除链表的倒数第N个数-LeetCode19

一、题目描述

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

二、解题思路

1、利用快慢指针（重点！设置哑结点：当涉及可能对头结点进行删除等操作时，可以创建该辅助结点）

2、利用栈的思想：先全部入栈，然后出栈n个元素，此时的栈顶元素刚好为被删节点前的一个元素
（注意！也需要设置哑结点）

?三、代码实现

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        Deque<ListNode> deque = new LinkedList<>();
        ListNode record = dummy;
        while (record != null) {
            deque.push(record);
            record = record.next;
        }
        for (int i = 0; i < n; i++) {
            deque.pop();
        }
        ListNode pre = deque.peek();
        pre.next = pre.next.next;
        ListNode res = dummy.next;
        return res;
    }
}