【数据结构】单链表—求链表中间节点（只遍历一次链表）— 快慢

题目：给出一个单链表的，不知道结点N的值，怎样只遍历一次就可以求出中间结点。

我们可以定义两个指针，快指针和慢指针，都从头开始遍历链表，快指针每次走两步，慢指针每次走一步，当快指针走到结尾时，慢指针指向的便是链表的中间节点。

代码如下：

template<class T>
struct ListNode
{
    T _value;
    ListNode<T>* _next;

    ListNode(const T& value)
        :_value(value),_next(NULL)
    {}
};

template<class T>
class List
{
public:
    List()
        :_head(NULL)
    {}
    bool PushBack();
    ListNode<T>* FindMidNode()
    {
        ListNode<T>* fast = _head;
        ListNode<T>* slow = _head;
        while(fast && fast->_next)
        {
            slow = slow->_next;
            fast = fast->_next->_next;
        }
        return slow;
    }

private:
    ListNode<T>* _head;
};