【刷题日记】进阶版本的 19. 删除链表的倒数第 N 个结点

本次刷题日记的第 19 篇，力扣题为：进阶版本的 19. 删除链表的倒数第 N 个结点 ，中等

一、题目描述：

我们上一题做了 19. 删除链表的倒数第 N 个结点 ，做完了之后，xdm 有没有发现，我们其实是扫描了 2 次链表的，如果链表比较长的话，其实这种方式还是比较低效的

题目中有说到，我们是否可以使用一次扫描实现这套题？

能实现吗？必须能实现呀，咱们刷一个题不是刷完就完了的，还需要去分析他如何去解决才会更好更快，更健壮

就像工作中，咱们做一件事情，不是做完了就算了，还需要复盘，总结高效的经验的

1、这道题考察了什么思想？你的思路是什么？

我们也刷了一遍这个题了，那么我们如何只遍历一次链表，就能实现呢？

根据上次我们刷题的经验，我们知道如何找到找到倒数第 n 个节点，并删除他

我们先计算了 整个链表的长度，然后通过计算，算出了我们需要从头偏移多少次

那么这一次，我们是否可以在从头偏移指针的时候，我们自己就知道偏移到哪个位置就可以停下来呢？不需要去可以计算链表的长度

那么我们可以模拟一下：

看下图，如果有一个红指针和一个黑指针相差固定的距离，那么当黑指针先前走一步的时候，红指针也会向前走一步，直到黑指针都到链表尾部的时候，才会停止

那么这个时候，红指针和黑指针的距离一直是不会改变的，严格保持车距，不超车，也不会跟丢

我们回过头来思考一下，这个红指针是不是就相当于是倒数第 n 个节点呢？

如果我们要删除倒数第 n 个节点，那么我们也可以使用这样的方式，遍历一遍链表是不是就可以找到倒数第 n 个节点了呢？

那么同样的道理，既然我们是要删除倒数第 n 个节点，那么我们就要找到倒数第 n 个节点的前 1 个节点，这样便于我们链表操作的时候，删除需要删除的节点

那么，我们就直接一点，直接加入一个帮助节点，放到链表的头，让他从一开始就满足我们要找到删除节点的前一个节点，类似于下面这个样

上面紫色的节点便是我们需要删除的节点了，这一块的操作和之前的上一篇的做法一致，这里就不赘述了

那么接下来就是按照思路来翻译代码了 ， 这其实就是使用双指针的方式来处理这个题，关于双指针处理题目的场景还是非常多的

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码，注意快慢指针的处理

编码如下：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    // 定义一个帮助节点，放在整个链表的前面一个节点上，值域我们可以默认为0，定义为其他的数字也没有问题
    helper := &ListNode{0, head}
    // 定义一个快指针一个慢指针
    quick, slow := head, helper
    // 快指针先跑 n 次
    for i := 0; i < n; i++ {
        quick = quick.Next
    }
    // 快指针跑一次，慢指针跑一次，慢指针总是要多偏移 n+1 次才能追上 quick 指针
    for ; quick != nil; quick = quick.Next {
        slow = slow.Next
    }
    // 找到要删除节点是 慢指针的下一个节点
    slow.Next = slow.Next.Next
    return helper.Next
}

看了上述编码，还是比较清晰的吧，编码的逻辑和推演的逻辑一致，足够简单，足够好懂

只需要处理好 快慢指针的逻辑即可实现，这实现了扫描一边链表，便完成删除链表的倒数第 n 个节点，nice

四、总结：

该题的时间复杂度是 O(n) ，这个 n 是链表的长度，因为我们遍历了它，空间复杂度是 O(1) ，我们只引入了常数级别的空间消耗

原题地址：19. 删除链表的倒数第 N 个结点

今天就到这里，学习所得，若有偏差，还请斧正

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~