【萌新解题】删除链表的倒数第 N 个结点

关于我：微信公众号：面试官问，原创高质量面试题，始于面试题，但不止于面试题。【萌新解题】系列文章试图从新人的角度去看待和解决力扣题目，本题是力扣第 19 题 删除链表的倒数第 N 个结点：https://leetcode.cn/problems/remove-nth-node-from-end-of-list。

题目描述

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

前置知识点

很多链表相关的问题都可以使用双指针法来解决。双指针法可以根据两个指针不同的移动方式细分成两种不同的方法：

• 前后双指针：即一个指针在链表中提前朝着指向下一个节点的指针移动若干步，然后再同时移动第二个指针
• 快慢双指针：即两个指针在链表中移动的速度不一样，通常是快的指针朝着指向下一个节点的指针一次移动两步，慢的指针一次只移动一步。

解题说明

本题是前后双指针的典型应用，通常为了删除一个节点，应该找到被删除节点的前一个节点，然后把该节点的 next 指针指向它下一个节点的下一个节点，这样下一个节点没有被其他节点引用，也就相当于被删除了。 要删除链表倒数第 n 个节点，根据链表删除节点的特性，我们并不是直接找到要删除的这个节点，而是要找到倒数第 n+1 个节点，然后通过修改倒数第 n+1 个节点的指针实现删除倒数第 n 个节点。

代码如下所示：

class Solution {
    /**
     * 通常为了删除一个节点，应该找到被删除节点的前一个节点，然后把该节点的next指针指向它下一个节点的下一个节点，这样下一个节点没有被其他节点引用，也就相当于被删除了。 
     * 要删除链表倒数第 n 个节点，根据链表删除节点的特性，我们并不是直接找到要删除的这个节点
     * 而是要找到倒数第 n+1 个节点，然后通过修改倒数第 n+1 个节点的指针实现删除倒数第 n 个节点
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 引入哨兵节点，避免处理例如输入的链表为空，或者被删除的节点是原始链表的头节点等边界问题
        ListNode dummy = new ListNode();
        dummy.next = head;

        // 前指针
        ListNode first = head;

        // 后指针
        ListNode second = dummy;

        // 前指针先移动到 n-1 的位置
        for (int i=0; i<n; ++i) {
            first = first.next;
        }

        // 前后双指针同时移动，直到前指针到达链表尾部
        while (first != null) {
            first = first.next;
            second = second.next;
        }

        // 此时后指针已经指向倒数第 n+1 个节点，删除它的下一个节点也就是倒数第 n 个节点即可
        second.next = second.next.next;

        return dummy.next;        
    }
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的长度
• 空间复杂度：O(1)，没有使用额外的存储空间