快慢指针

• 输入链表头节点，奇数长度返回中点，偶数长度返回上中点
• 输入链表头节点，奇数长度返回中点，偶数长度返回下中点
• 输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
• 输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个

package mid;

public class LinkedListMid {
    /**
     * 输入链表头节点，奇数长度返回中点，偶数长度返回上中点
     *
     * @param root head
     *
     * @return 中点
     */
    public static Node midOrUpMidNode(Node root) {
        // 边界情况
        if (root == null || root.next == null || root.next.next == null) {
            return root;
        }
        // 快慢双指针
        Node slow = root.next;
        Node fast = root.next.next;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * 输入链表头节点，奇数长度返回中点，偶数长度返回下中点
     *
     * @param root head
     *
     * @return 中点
     */
    public static Node midOrDownMidNode(Node root) {
        // 边界情况
        if (root == null || root.next == null) {
            return root;
        }
        // 快慢双指针
        Node slow = root.next;
        Node fast = root.next;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * 输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
     *
     * @param root head
     *
     * @return 中点
     */
    public static Node midOrUpMidPreNode(Node root) {
        // 边界情况
        if (root == null || root.next == null || root.next.next == null) {
            return null;
        }
        // 快慢双指针
        Node slow = root;
        Node fast = root.next.next;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * 输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个
     *
     * @param root head
     *
     * @return 中点
     */
    public static Node midOrDownMidPreNode(Node root) {
        // 边界情况
        if (root == null || root.next == null) {
            return null;
        }
        if (root.next.next == null) {
            return root;
        }
        // 快慢双指针
        Node slow = root;
        Node fast = root.next;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public static class Node {
        public int value;
        public Node next;

        public Node(int v) {
            value = v;
        }
    }
}