19. 删除链表的倒数第 N 个结点（解法一：单调栈）

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

示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1
输出：[]
示例 3：
输入：head = [1,2], n = 1
输出：[1]
分析：
题目中提到“倒数”这个关键词，很容易想到可以使用栈这种数据结构，我们可以在遍历链表的同时将所有结点依次入栈。根据栈「先进后出」的原则，我们弹出栈的第 n个节点就是需要删除的节点，并且目前栈顶的结点就是待删除节点的前驱节点。
复杂度分析
时间复杂度：O(L)O(L)，其中 LL 是链表的长度。
空间复杂度：O(L)O(L)，其中 LL 是链表的长度。主要为栈的开销。

package com.codernav.demo.leetcode.linkedlist.removeElements;

import com.codernav.demo.common.ListNode;

import java.util.Stack;

/**
 * @title 19. 删除链表的倒数第 N 个结点（栈）
 * @Description 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 * @Author 开发者导航
 * @website https://www.codernav.com
 * @date 2023/3/4
 */
public class Q_19_2 {
    public static void main(String[] args) {
        ListNode node5 = new ListNode(5, null);
        ListNode node4 = new ListNode(4, node5);
        ListNode node3 = new ListNode(3, node4);
        ListNode node2 = new ListNode(2, node3);
        ListNode node1 = new ListNode(1, node2);
        // 双指针
        ListNode head = removeNthFromEnd(node1, 2);
        System.out.println(head);
    }

    public static ListNode removeNthFromEnd(ListNode head, int n) {
        // 虚拟结点
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;

        // 将结点放入栈（包括虚拟结点）
        Stack<ListNode> stack = new Stack<>();
        ListNode curr = dummyNode;
        while (curr != null) {
            stack.push(curr);
            curr = curr.next;
        }

        // 移除最后n个元素
        for (int i = 0; i < n; i++) {
            stack.pop();
        }
        // 找到要移除元素的前驱元素
        ListNode prev = stack.peek();
        // 删除结点
        prev.next = prev.next.next;

        return dummyNode.next;
    }
}