链表中间节点思路

找链表的中间节点，可以依赖快慢指针来求解。
思路是：一个慢指针，从head开始一次走 1 步；另外一个快指针，从head还是一次走 2 步。当快指针走到末尾的时候，那么慢指针刚好在中间位置。

该算法思路，可以用简单的路程计算来理解：假设一段路程，长度是L，从起始点开始，路人甲要走到中间的位置停止。但是路人甲不知道该段路程是多远，因此他也不知道要走到哪个位置停止。这时来了路人乙，他走到比较快，他愿意帮助路人甲确定位置。怎么确定呢？

假设路人甲走到中间位置的用时记做： time，速度记做：speed甲，走的路程长度记做：L/2

这时，路人乙就想了，如果他和路人甲同时走，行走的时间都是 time。如果路人乙在 time 节点时，刚好走到了终点停止(这样他就有参照了可以打电话告诉路人甲也要停止走动了)，那路人甲肯定就刚好走到了中间的位置！那路人乙的行走速度应该是多少可以保证这样的节点不会出错呢？因为太快的话，可能路人甲还没有到中间位置，太慢的话，路人甲可能已经超过了中间位置。

所以问题就变成了计算路人乙的行走速度： speed乙

根据上面的已知条件，可以很快得出下面两个等式：

① speed甲 * time = L/2;
② speed乙 * time = L；

由 ①② 可以得出：

speed乙 == 2 * speed甲;

从上面的计算结果可以知道，路人乙的速度需要是路人甲的 2倍

应用到链表上。由于每次只能挨个遍历链表的节点，所以慢指针的速度就是 每次向后走1步，快指针的速度就是慢指针的 2倍，也就是每次走 2 步了。

代码：

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

代码来源：https://leetcode-cn.com/problems/middle-of-the-linked-list/solution/lian-biao-de-zhong-jian-jie-dian-by-leetcode-solut/