给定一个非空单链表，返回中间节点。

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

例一：
输入： [1,2,3,4,5]
输出： 值为 3 的节点

例二：
输入： [1,2,3,4,5,6]
输出： 值为 4 的节点

提示：
链表的长度在 1 到 100 之间。

常用方法，快慢法，使用速度为 1 和 2 的两个节点来遍历链表，当快节点跑完了整个链表，慢节点就是中间节点。

/*
 * 876. Middle of the Linked List
 * https://leetcode.com/problems/middle-of-the-linked-list/
 * https://www.whosneo.com/876-middle-of-the-linked-list/
 */

public class MiddleNode {
    public static void main(String[] args) {
        MiddleNode solution = new MiddleNode();

        ListNode head = new ListNode(1);
        ListNode node = head;
        for (int i = 2; i < 7; i++) {
            node.next = new ListNode(i);
            node = node.next;
        }

        solution.print(head);
        node = solution.middleNode(head);
        solution.print(node);
    }

    private void print(ListNode node) {
        for (; node != null; node = node.next) {
            System.out.print(node.val);
            System.out.print("->");
        }
        System.out.println("null");
    }

    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;
    }
}