快、慢指针题目示例（C++）

由一个题目引出概念

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

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

输出：[3,4,5]

解释：链表只有一个中间结点，值为 3 。

示例 2：

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

输出：[4,5,6]

解法一：朴素解法

这道题最朴素的做法是，先遍历一次，计算链表的长度，进而计算链表中间结点的下标（注意偶数结点的时候，得到的是中间的第二个结点），然后再遍历一次，来到所要求结点的位置。

缺点：必须先遍历完整个链表，然后才可以「干正事」，再遍历到一半，找到中间结点；

在链表的长度很长的时候，这种方法之前的等待会很久。

代码略

解法二：快慢指针法

设置两个指针，一个fast，每次走两步，一个slow，每次走一次，这样当fast走到最后的时候，slow就刚好走到一半

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

时间复杂度为O（N），空间复杂度为O（1）

方法三：数组法

这种也是我们最容易想到的方法，把链表存在数组里，然后输出中间的元素

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        vector<ListNode*> A = {head};
        while (A.back()->next != NULL)
            A.push_back(A.back()->next);
        return A[A.size() / 2];
    }
};

时间复杂度为O（N），空间复杂度为O（N），不如快慢指针法。

总结：

快慢数组法可以节省空间，只用两个指针就可以完成查找任务。