【初阶数据结构】——leetcode：链表的中间结点

1. 题目介绍

链接: link

我们一起来看一下题目：

题目给我们一个链表，要求我们返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。

2. 思路分析——快慢指针

题目其实挺简单的，但是我们比较容易想到的都是比较暴力的解法：

比如我们可以先遍历一遍求出链表的长度，然后求出中位数，再遍历寻找并返回对应的结点。

那我们来加一点挑战性，如果要求只能遍历一遍，要如何解决呢？

那么比较经典的一种思路就是快慢指针。
大致的思路是这样的：
定义两个“指针”：快指针fast，慢指针slow。两个指针都从第一个结点开始往后走，慢指针一次走一步，快指针一次走两步，这样快指针走到终点的时候，慢指针刚好就在中间位置。

那具体我们来画图分析一下：
那这里要分为两种情况：链表结点的个数为奇数个或者为偶数个。
首先来看如果是奇数个，比如：

fast和slow都从第一个结点开始。
fast一次走两步，slow一次走一步

我们看到这样最终fast走到结尾的时候（即fast->next＝＝NULL），slow就正好处在链表的中间结点。

那如果结点的个数是偶数呢？

像这样。
我们再来画一下：

我们发现如果是奇数个，fast最后正好可以走到最后一个结点的位置；而如果是偶数的话，fast就走到最后一个结点的下一个，就是NULL。（即fast==NULL时结束）
而此时slow的位置也是正确的，因为题目要求如果有两个中间结点，则返回第二个中间结点。
我们看到slow正好处在第二个中间结点。

3. 代码实现

那我们来实现一下代码：

没问题，通过了。

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* slow=head;
    struct ListNode* fast=head;

    while(fast && fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
    }

    return slow;
}

4. 思维拓展

刚才这道题目中要求如果两个中间结点的话（那就是偶数个结点），要返回的是第二个中间结点。

那我们上面的快慢指针的思路fast一次走两步，刚好偶数个的话，fast会停在最后一个结点的下一个位置（即fast==NULL时结束），此时slow刚好指向第二个中间结点。

那么，如果我现在要求偶数个的话，返回第一个中间结点，怎么做呢？

如果是这样的话比较简单的一个思路就是可以再增加一个指针prev，记录slow指针的前一个结点。

这样的话如果最终是fast为空，那就是偶数个，我们就返回prev（就是第二个中间结点），如果是fast->next为空，那就是奇数个，还是返回slow。