單連結清單–快慢指針（中間值，是否有環，環的入口）

​ 快慢指針指的是定義兩個指針，這兩個指針的移動速度一塊一慢，以此來制造出自己想要的內插補點，這個內插補點可以然我們找到連結清單上相應的結點。一般情況下，快指針的移動步長為慢指針的兩倍

中間值問題(代碼見最後)

​ 利用快慢指針，我們把一個連結清單看成一個跑道，假設a的速度是b的兩倍，那麼當a跑完全程後，b剛好跑一半，以此來達到找到中間節點的目的。

​ 如下圖，最開始，slow與fast指針都指向連結清單第一個節點，然後slow每次移動一個指針，fast每次移動兩個指針。

單向連結清單是否有環問題

​ 使用快慢指針的思想，還是把連結清單比作一條跑道，連結清單中有環，那麼這條跑道就是一條圓環跑道，在一條圓環跑道中，兩個人有速度差，那麼遲早兩個人會相遇，隻要相遇那麼就說明有環。

有環連結清單入口問題

​ 當快慢指針相遇時，我們可以判斷到連結清單中有環，這時重新設定一個新指針指向連結清單的起點，且步長與慢指針一樣為1，則慢指針與“新”指針相遇的地方就是環的入口。

/**
 * 單連結清單--快慢指針
 * 解決的問題：中間值問題，是否有環問題，有環連結清單入口問題
 */
public class FastSlowTest {
    public static void main(String[] args) {
        Node<String> first = new Node<String>("aa", null);
        Node<String> second = new Node<String>("bb", null);
        Node<String> third = new Node<String>("cc", null);
        Node<String> fourth = new Node<String>("dd", null);
        Node<String> fifth = new Node<String>("ee", null);
        Node<String> six = new Node<String>("ff", null);
        Node<String> seven = new Node<String>("gg", null);

        // 完成結點之間的指向
        first.next = second;
        second.next = third;
        third.next = fourth;
        fourth.next = fifth;
        fifth.next = six;
        six.next = seven;

        // 查找中間值（此時連結清單無環）
        String mid = getMid(first);
        System.out.println("中間值為：" + mid);

        // 産生環
        seven.next = third;
        // 判斷連結清單是否有環
        boolean circle = isCircle(first);
        System.out.println("連結清單中是否有環：" + circle);

        // 找到有環連結清單入口
        Node entrance = getEntrance(first);
        System.out.println("有環連結清單的入口：" + entrance.item);

    }

    /**
     * 查找有環連結清單中環的入口結點
     *
     * @param first 連結清單首結點
     * @return 環的入口結點
     */
    public static Node getEntrance(Node<String> first) {
        // 定義兩個指針（實質就是結點）
        Node<String> slow = first;
        Node<String> fast = first;
        Node<String> temp = null;  // 有環時才會讓temp指向第一個結點
        // 周遊連結清單，先找到環（快慢指針相遇），準備一個臨時指針，指向連結清單的首屆點，繼續周遊，直到慢指針與臨時指針相遇，相遇的結點就是環的入口
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast.equals(slow)) {
                temp = first; // 有環時才會讓temp指向第一個結點
                continue;
            }
            // 讓臨時指針變換（fast與slow不相等時，每次循環到這裡因temp=null，是以不會變換）
            if (temp != null) {
                temp = temp.next;
                // 判斷臨時指針是否與滿指針相遇，相遇即為環的入口
                if (temp.equals(slow)) {
                    return temp;
                }
            }
        }
        return null;
    }

    /**
     * 判斷連結清單中是否有環
     *
     * @param first 連結清單首結點 * @return ture為有環，false為無環
     */
    public static boolean isCircle(Node<String> first) {
        // 定義兩個指針（實質就是結點）
        Node<String> fast = first;
        Node<String> slow = first;
        // 周遊連結清單，如果快慢指針指向同一個結點，證明有環
        while (fast != null && fast.next != null) {
            // 變換fast和slow的值
            fast = fast.next.next;
            slow = slow.next;
            if (fast.equals(slow)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 查找中間值
     *
     * @param first 連結清單的首結點
     * @return 連結清單的中間結點的值
     */
    public static String getMid(Node<String> first) {
        // 定義兩個指針（實質就是結點）
        Node<String> fast = first;
        Node<String> slow = first;
        // 使用兩個指針周遊連結清單，當快指針指向的結點沒有下一個結點就可以結束了，結束後滿指針指向的結點就是中間值
        while (fast.next != null && fast != null) {
            // 變換fast和slow的值
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow.item;
    }

    // 結點類
    private static class Node<T> {
        // 存儲資料
        T item;
        // 下一個結點
        Node next;

        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
}