题目大意：
链表的中间结点
给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：[1,2,3,4,5] 输出：此列表中的结点 3 (序列化形式：[3,4,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。 注意，我们返回了一个 ListNode 类型的对象 ans，这样： ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：
输入：[1,2,3,4,5,6] 输出：此列表中的结点 4 (序列化形式：[4,5,6]) 由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
提示：
- 给定链表的结点数介于
1和100之间。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=876
解题思路分析：
本题解法有很多种，最简单的便是遍历一遍链表，将其中的所有节点都存储值List中，然后选取List中间的那个元素即可。不过这样会比较浪费存储空间。因此我们可以采用递归的方式优化算法。
解法一：递归
我们建立一个递归函数，它的返回值是链表最尾元素的下标，我们给递归函数传入当前节点，以及当前节点所在下标，起始时，节点为根节点，下标为0，递归函数中，如果当前节点没有下一个节点，那么说明当前节点即是尾节点，当前的下标也即是链表的尾元素下标。如果当前节点不是尾元素，那么我们将当前元素的下一个节点以及当前下标加一作为参数递归至子方法中，递归子函数的返回值即是尾元素下标。接下来我们查看当前下标是否为尾元素下标的中间值，如果是的话，当前元素即是返回结果。
实现代码：
ListNode res; // 返回结果
public ListNode middleNode(ListNode head) {
help(head, 0); // 递归
return res;
}
// head：当前节点
// index：当前下标
int help(ListNode head, int index){
int lastIndex; // 链表尾元素下标
// 如果当前元素是尾元素，lastIndex是当前下标
if(head.next==null) lastIndex = index;
// 否则递归至下一个元素，返回值为尾元素下标
else lastIndex=help(head.next, index+1);
// 如果当前元素是尾元素下标的中间值，当前节点即是返回结果
if(index==(lastIndex+1)/2) res = head;
// 返回尾元素下标
return lastIndex;
}本题解法执行时间为0ms。
Runtime: 0 ms, faster than 100.00% of Java online submissions for Middle of the Linked List.
Memory Usage: 36.7 MB, less than 7.84% of Java online submissions for Middle of the Linked List.
解法二：双指针（快慢指针）
本题的最优解法应该是利用快慢双指针来解题。题目求的是链表中间节点，那么我们可以定义快和慢两个指针，慢指针每次向后走一步，快指针每次向后走两步，当快指针走到链表尾部时，慢指针应正好走到链表的中间位置（速度是快指针的一半）。
实现代码：
public ListNode middleNode(ListNode head) {
ListNode slow=head, fast=head;
while(fast != null && fast.next != null){
slow=slow.next;
fast=fast.next.next;
}
return slow;
}本题解法执行时间为0ms。
Runtime: 0 ms, faster than 100.00% of Java online submissions for Middle of the Linked List.
Memory Usage: 36.7 MB, less than 7.84% of Java online submissions for Middle of the Linked List.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-876-middle-of-the-linked-list-解题思路分析/