部分数据结构请看常见Java问题及笔试题（二十一），这里只列出主要方法与测试用例！！！

寻找单链表的中间节点，最简单的思路就是：（1）第一次遍历链表，求出长度n，第二次遍历n/2的距离即可。（2）其实还有一个比较巧的思路是，用两个指针，同时从头结点开始遍历，一个指针一次走一步，一个指针一次走两步，如果链表长度为奇数，则当快指针走到最后一个结点的时候，慢指针指向中间结点，当链表长度为偶数的时候，当快指针走到最后的时候，中间结点就是慢指针指向的结点以及慢指针指向的节点的下一个结点。

下面先来看第一种思路，代码如下：

输出结果

下面来看一下方法2的做法，代码如下：