【LeetCode】返回链表的中间结点、删除链表的倒数第 N 个结点

主页：HABUO🍁主页：HABUO

🌜钱塘江上潮信来，今日方知我是我🌛

1.返回链表的中间结点

题目：给你单链表的头结点 head ，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

示例：

输入：head = [1,2,3,4,5]       输出：[3,4,5]       解释：链表只有一个中间结点，值为 3 。

输入：head = [1,2,3,4,5,6]    输出：[4,5,6]       解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

分析：我们要找到中间节点，是不是有两种可能性，节点数为奇数和偶数两种，奇数的话很简单就是中间的节点，偶数是不是中间就有两个节点，根据题中意思，我们需要返回的是这两个节点中的第二个节点，我们的方法是采用两个伪指针的方法，什么意思呢？就是说，两个伪指针刚开始都指向我们的头指针，走的过程中，快指针走两步，慢指针走一步，当快指针走完整个链表的时候，它们的差是不是就是整个链表的一半，这就是我们的思路，具体可看下图：

当然这里快指针走向最后的时候有些细节需要注意，奇数的话当slow走向中间节点的时候，fast刚好走向最后一个节点，也即是fast->next = NULL，奇数情况见下图，但是这个偶数情况fast就跑到链表之外，如果再进行访问就会造成对NULL访问的错误，因此处理方法见下：

fast != NULL && fast->next != NULL

综上，我们的总体代码如下：

struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while(fast != NULL && fast->next != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

2.删除链表的倒数第 N 个结点

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

示例：

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

输入：head = [1], n = 1 输出：[]

输入：head = [1,2], n = 1 输出：[1]

分析：这个题我们乍一看是不是上一个题的进阶版啊🤭，没错，这就是上一个题的通用版，会了这个题是不是，无论它让找第几个节点，我们都能找到😁。现在就让我们领略这道题的神奇，我将以两种方法去讲解，第二种方法也是第一种方法的进阶。根据上一题的思路，我们仍然采用双指针去找到倒数第n个节点，我们该怎么想呢？上一题因为它们走的步差到最后刚好一半，那这道题是不是也是这种思路呢？没错就是这种思路，不过和上道题不同的是这次我们让它一开始就差距n步，那fast走到最后，因为差了n步，slow是不是就恰好在倒数第n个节点的位置，对就是这种思路🌞。因为这道题需要我们去删除，因此我们还应该需要一个伪指针指向slow前一个节点。整体思路见下：

这里需要注意虽然n=2，即是让我们去删除倒数第二个节点，但是倒数第一个和第二个之间是不是就一步，因此我们只需要让fast先走一步即可，所以总体思想见下：

struct ListNode* fast = head;
struct ListNode* slow = head;
struct ListNode* prev = NULL;
while (--n)//fast与slow相差的步数
{
    fast = fast->next;
}
while (fast->next != NULL)
{
    fast = fast->next;
    prev = slow;
    slow = slow->next;
}
prev->next = slow->next;
free(slow);
slow = NULL;
return head;

实现了上面的代码就大功告成了吗？其实这只是最正常的情况，只是我们让fast和slow动了起来，还有许多的细节没考虑到，例如：如果只有一个节点怎么办？我们要删最后一个节点怎么办？我们要删大于一个节点的头节点怎么办？好不容易有了思路，怎么还有这么多细节要考虑，是不是有点烦🫥，我劝你别烦，我们来一步一步的分析：

第一个问题：如果只有一个节点怎么办？如下所示：

如果用上面的代码两个while循环都没有进去，下面紧接着就是prev->next，立马就出现对NULL解引用的错误，还有下面 free(slow)，空间还给了内存，我们的head和fast成了野指针了，是不是都是问题，所以们需要另外考虑一下这个情况，解决如下：

head = slow->next;
free(slow);
slow = NULL;
fast = NULL;
return head;

第二个问题：如果要删最后一个节点怎么办？如下所示：

这个问题只需要将我们最正常情况加上一句fast = NULL，为了防止fast成为野指针。

至于第三个问题如果我们要删大于一个节点的头节点，其实在上述头节点的删除过程中已经解决，因为上述代码的妙处就在于head = slow->next在free(slow)之前，如果在它之后，是不是就要两种情况，因为slow后面又可能为NULL又可能不为NULL。因此头尾解决好，就剩下正常思路我们一开始就解决的了，所以这个问题就已经迎刃而解了，总体代码见下：

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    struct ListNode* prev = NULL;
    while (--n)
    {
        fast = fast->next;
    }
    while (fast->next != NULL)
    {
        fast = fast->next;
        prev = slow;
        slow = slow->next;
    }
    if (prev == NULL)//头删
    {
        head = slow->next;
        free(slow);
        slow = NULL;
        fast = NULL;
        return head;
    }
    else//正常删+尾删
    {
        prev->next = slow->next;
        free(slow);
        slow = NULL;
        fast = NULL;
        return head;
    }
}

方法二：带有哨兵位的双指针法 

分析：上面我们看到又是这种细节需要考虑，又是那种细节要考虑，是不是挺令人讨嫌😒，因此我们设置一个哨兵位节点放置在头节点处，那prev就不可能为NULL，这还考虑prev为不为NULL干什么，让它一边去！思路见下：

此时无论怎么样，prev都不可能为NULL，想怎么访问就怎么访问，上面的方法麻烦就麻烦在prev有两种可能性，但这个方法需要注意的是我们返回的是head->next，还需要注意进入循环之前把prev和head安排好，具体见下：

struct ListNode* prev = (struct ListNode*)malloc(sizeof(struct ListNode));
prev->next = head;
head = prev;
return head->next;

其它和我们上个方法正常情况是一样的。总体代码见下：

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    struct ListNode* prev = (struct ListNode*)malloc(sizeof(struct ListNode));
    prev->next = head;
    head = prev;
    while (--n)
    {
        fast = fast->next;
    }
    while (fast->next != NULL)
    {
        fast = fast->next;
        prev = slow;
        slow = slow->next;
    }
    prev->next = slow->next;
    free(slow);
    slow = NULL;
    return head->next;
}

🍁时间可以伸缩和折叠，唯独不能倒退🍁

🌟不要温和地走进那个良夜🌟