算法题目
链表中的中间节点：
给定一个带有头结点 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 之间。
测试用例
[3,4,5] [2] [1,2,3,4]
思路分析
解法一：根据链表长度
思路：首先遍历链表得到链表的长度，根据链表长度再次遍历得到中间结点
分析：时机复杂度为n级，不需额外的空间，但是会遍历一次半链表
解法二：双指针法
思路：利用两个指针，一个快指针，一个慢指针，慢的每次后移一次，快的每次后裔两次，当快指针遍历结束返回慢指针
分析：时间复杂度为n级，不需要额外的内存空间
思考：由于链表的长度为偶数或者奇数，所以在快慢指针移动上面要注意这一点的处理
//测试函数
import com.test.day6_22.ListNode;
/**
@author cosefy
@date 2020/6/23
*/
public class GetMiddleNode {
public static void main(String[] args) {
int[] nums = {1, 3, 4, 5};
ListNode head = getLinkedList(nums);
ListNode middle_node1 = test1(head);
ListNode middle_node2 = test2(head);
System.out.println("解法一的中间结点结果：" + middle_node1.val);
System.out.println("解法二的中间结点结果：" + middle_node2.val);
}
//根据数组创建链表，返回头结点
public static ListNode getLinkedList(int[] nums) {
ListNode head = new ListNode(nums[0]); //链表长度在1-100之间
ListNode L = head;
for (int i = 1; i < nums.length; i++) {
ListNode node = new ListNode(nums[i]);
L.next = node;
L = L.next;
}
return head;
}
}
//解法一：根据链表长度
public static ListNode test1(ListNode head) {
int count = 0;
ListNode L = head;
while (L != null) {
++count;
L = L.next;
}
count = count / 2 + 1;
while (count > 1) {
head = head.next;
--count;
}
return head;
}
//解法二：双指针
public static ListNode test2(ListNode head) {
ListNode fast_node = head, slow_node = head;
while (fast_node.next != null) {
fast_node = fast_node.next;
slow_node = slow_node.next; //这里的处理方式是先让快指针移动，再慢指针，再快指针。
if (fast_node.next != null)
fast_node = fast_node.next;
}
return slow_node;
}