链表--[19]删除链表的倒数第 N 个节点/medium

1、题目

给你一个链表，删除链表的倒数第?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]

?

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

?

进阶：你能尝试使用一趟扫描实现吗？

2、题目分析

1、删除链表节点，需要定位到待删节点前面的一个节点（仅定位到待删节点是不够的）。
2、因为被删节点可能是头结点，故没有前面的节点，需要特殊处理。我们可以运用哨兵头结点，简化链表代码的编写。
3、对于链表这种数据结构，如果需要遍历到尾部才能开始处理数据，则考虑使用回溯思想来考虑问题。

3、解题步骤

1、创建哨兵节点，并指定为链表头结点
2、设计递归方法的入参和出参：入参-当前node节点，待删节点数n；出参-该节点属于链表的倒数第几个节点
3、递归结束条件：遍历到链表尾部，并返回1，表示上一个节点是倒数第1个节点
4、递归前的操作：无
5、递归后的操作：基于递归返回值，可知道当前是倒数第几个节点。再与待删除的倒数节点数做对比。如果当前节点是待删节点的上一个节点。则可开始删除待删节点

4、复杂度最优解代码示例

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode sentinel = new ListNode();
        // 1、创建哨兵节点，并指定为链表头结点
        sentinel.next = head;
        remove(sentinel, n);
        return sentinel.next;
    }

    /**
     * 2、设计递归方法的入参和出参：入参-当前node节点，待删节点数n；出参-该节点属于链表的倒数第几个节点
     */
    public int remove(ListNode node, int n) {
        if (node == null) {
            // 3、递归结束条件：遍历到链表尾部，并返回1，表示上一个节点是倒数第1个节点
            return 1;
        }
        // 4、递归前的操作：无

        int th = remove(node.next, n);
        if (th == n + 1) {
            // 5、递归后的操作：基于递归返回值，可知道当前是倒数第几个节点。再与待删除的倒数节点数做对比。如果当前节点是待删节点的上一个节点。则可开始删除待删节点
            node.next = node.next.next;
        }
        return th + 1;
    }

5、抽象与扩展

1、使用哨兵作为头节点，以此简化链表代码：处理链表时，如果 头结点和其他节点的处理逻辑不一致
2、用回溯思想来考虑问题：对于链表这种数据结构，如果需要遍历到尾部才能开始处理数据