【LeetCode 刷题日】19.删除链表的倒数第n个节点

前言： 继续对链表的学习，暴打LeetCode，接下来就快到了哈希表，其实我在写这些算法之前，看过一些关于数据结构的书，有的书上来就是摆一堆源码，看的迷迷糊糊的，有的又太过于简单了，目前还没找到很合适的书，有没有大佬有推荐的，以及一些计算机基础四大件的数据。

题目背景：LeetCode19

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 进阶：你能尝试使用一趟扫描实现吗？ 示例 1：

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

输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5] 示例 2： 输入：head = [1], n = 1 输出：[] 示例 3： 输入：head = [1,2], n = 1 输出：[1]

题目答案：

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //新建一个虚拟头节点指向head
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        //快慢指针指向虚拟头节点
        ListNode fastIndex = dummyNode;
        ListNode slowIndex = dummyNode;

        // 只要快慢指针相差 n 个结点即可
        for (int i = 0; i <= n; i++) {
            fastIndex = fastIndex.next;
        }
        while (fastIndex != null) {
            fastIndex = fastIndex.next;
            slowIndex = slowIndex.next;
        }

        // 此时 slowIndex 的位置就是待删除元素的前一个位置。
        // 具体情况可自己画一个链表长度为 3 的图来模拟代码来理解
        // 检查 slowIndex.next 是否为 null，以避免空指针异常
        if (slowIndex.next != null) {
            slowIndex.next = slowIndex.next.next;
        }
        return dummyNode.next;
    }
}

题目解析：

双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。思路是这样的，但要注意一些细节。

这时就有同学不理解，为什么快指针要先走n步，当然快指针肯定是比慢指针快的，从名字就看出来了，但具体原理是什么呢？

简单的来说：先走n步，就是为了制造快慢指针之间的间距，那为什么要制造间距呢，首先要明确题目要干嘛，要删除倒数第n个节点，根据链表的特性，我们删除一个节点必须要知道这个节点的前驱节点，所以我们做的一切都是为了让慢指针最后停在要删除节点的前置节点那个位置。这样才能 slow.next = slow.next.next 删掉目标节点。

因此我们看流程：

图解：为什么快指针要先走 n 步？

举个最清晰的例子：链表：1 → 2 → 3 → 4 → 5，n = 2要删除：倒数第 2 个节点 4

初始状态

plaintext

fast
slow
  ↓
  1 → 2 → 3 → 4 → 5 → null

① 快指针先走 n 步（n=2，走 2 步）

plaintext

          fast
slow
  ↓        ↓
  1 → 2 → 3 → 4 → 5 → null

👉 此时快慢相差 n 个节点

② 快慢一起走，直到 fast 到末尾

plaintext

                      fast
          slow
          ↓           ↓
  1 → 2 → 3 → 4 → 5 → null

👉 slow 正好停在 3，是 4 的前一个！

③ 删除

plaintext

slow.next = slow.next.next

结果：1 → 2 → 3 → 5 → null

先走 n 步 =也就是为了拉开 n 步距离

一起走到头 代表着 慢指针刚好落在倒数第 n 个的前一个

没有这 n 步，我们根本定位不到要删的节点

因此我们在代码里的for循环就是为了提前让快节点先走n次领先

条件理解：

fast.next != null的意思是快节点还没走到最后一个节点，因为最后一个节点的下一个就是null，链表默认的

if (slowIndex.next != null)这里if里面的条件判断是为了防止空指针异常也就是为了防止

slow.next.next;空指针

关于这里的虚拟头节点，我们已经很清楚了，它仅仅是为了让头节点与其他的节点平级。

结语：如果对你有帮助，请点赞，关注，收藏，你的支持就是我最大的鼓励！