111.删除链表倒数第 n 个结点

今天（2020-08-26）写完一个简单的链表题：删除链表的倒数第 n 个结点
思路也非常简单（暴力找长度，然后与 n 相减得到对应的答案，就不说了）：

• 设置两个指针：quick 和 slow，共同指向链头。
• quick 先走 n 步。
• quick 和 slow 一起走，直到 quick 走到链尾。
• slow 指向的结点就是要删除的结点。

根据上述思路，我就写出了自己的第一个版本：

void removeNthFromEnd1(node** head_ref, int n)
{
    if (n == 0) return ;
    node* slow = *head_ref;
    node* quick = *head_ref;
    for(int i=0; i<n; ++i) { // 这里循环 n 次
        quick = quick->next;
    }
    if (quick == NULL) {
        *head_ref = slow->next;
        return ;
    }
    while(quick->next != NULL) {
        quick = quick->next;
        slow = slow->next;
    }
    slow->next = slow->next->next;
}

可以看到上面会有很多判断边界条件的地方，并且不同的情况需要不同处理，这里是指，当要删除第一个元素的时候。
故可以引入哑结点（dummy node）也可以称之为头结点，来处理上述边界问题：

void removeNthFromEnd2(node** head_ref, int n) // 使用哑结点
{
    if (n == 0) return;
    node* dummy = (node*)malloc(sizeof(node));
    dummy->next = *head_ref;
    node* slow = dummy;
    node* quick = dummy;
    for(int i=0; i<=n; ++i) { // 加入 dummy ，故要循环 n + 1 次
        quick = quick->next;
    }
    while(quick != NULL) {
        quick = quick->next;
        slow = slow->next;
    }
    slow->next = slow->next->next;
    *head_ref = dummy->next;
}

加入哑结点了之后，就不用写 if 来判断删除的是否为第一个结点了。不过代码也并没有减少多少。
随后看了题解之后，看到一个很巧妙的写法：

void emoveNthFromEnd3(node** head_ref, int n)
{
    if (n == 0) return ;
    node* quick = *head_ref;
    node* slow = *head_ref;
    while(quick) {
        if (n < 0) slow = slow -> next; // 当 quick 前进 n + 1 步，slow 才能走。
        quick = quick->next;
        --n;
    }
    if (n == 0) *head_ref = slow->next;
    slow->next = slow->next->next;
}

这里是直接遍历循环整个 quick ，同时记录下前进的步数。当 quick 前进 n+1 步时，slow 就能跟着一起走了。
关于为什么是 n+1 步。如果你要删除倒数第 n（n 小于或等于链表长度）个结点，quick 就要先走 n 步。然后，quick 和 slow 一起走，这样一个问题就是，slow 走到了你要删除结点的位置。如果你写过链表，就知道，要删除一个结点，必须获得该结点的前一个结点才能删除。所以让 quick 走 n+1 步，以达到 slow 少走一部的效果。
这里走 n+1 步也非常巧妙：先判断，再减减。
当然，你可以将判断和减减写在一行，不过这样代码可读性太差了：

if (n-- < 0) slow = slow ->next;

我个人觉得，循环遍历整个链表的方法已经很不错了。当然还可以将上述方法加上哑结点：

void removeNthFromEnd4(node** head_ref, int n)
{
    if (n == 0) return;
    node* dummy = (node*)malloc(sizeof(node));
    dummy->next = *head_ref;
    node* slow = dummy;
    node* quick = dummy;
    while(quick) {
        if (n < 0) slow = slow->next; // 同样是 n + 1 步
        n--;
        quick = quick->next;
    }
    slow->next = slow->next->next;
    *head_ref = dummy->next;
}

这里还是 n+1 步，因为加入哑结点并不会影响遍历的结果，quick 和 slow 会共同遍历掉哑结点。其实这里无论加入多少个哑结点，同样是 quick 先走 n+1 步，slow 再跟着走。直到 quick 遍历完整个链表。也就是 quick 和 slow 的相对位置为 n+1 ，因为 quick 总是回到链尾的 NULL 结点，而 n 正好是要删除的那个数，所以加上一使得 slow 正好位于要删除结点的前一位，使得删除结点变得简单。
可以注意到，leedcode 上题目得函数声明是使用得指针函数：

node* removeNthFromEnd(node* head, int n)

而我写得函数都是使用的双指针：

void removeNthFromEnd(node** head, int n)

我相信聪明的你，会将两者互相转换。
上述代码，再以下代码的基础上运行：

#include <stdio.h>
#include <stdlib.h>
struct Node {
    int data;
    struct Node* next;
};
typedef struct Node node;