利用快慢指针解决中间值问题，单向链表是否有环问题以及有环链表入口问题

  1. 中间值问题；

  2. 单向链表是否有环问题；

  3. 有环链表入口问题；

  快慢指针： 快慢指针指的是定义两个指针，这两个指针的移动速度一快一慢，以此来制造出自己想要的差值，这个差值可以让我们找到链表是哪个相应的结点，已满情况下，快指针的移动步长为慢指针的两倍。

  中间值问题：

  当快指针走到尾部的时候，慢指针恰恰走到中间的位置；

  代码如下：

   public class FastSlowTest {

        public static void main(String[] args) {
            Node first = new Node("aa", null);
            Node second = new Node("bb", null);
            Node third = new Node("cc", null);
            Node fourth = new Node("dd", null);//
            Node fifth = new Node("ee", null);
            Node sixth = new Node("ff", null);
            Node seventh = new Node("gg", null);
            //完成结点之间的指向
            first.next = second;
            second.next = third;
            third.next = fourth;
            fourth.next = fifth;
            fifth.next = sixth;
            sixth.next = seventh;
            
         //查找中间值,在查找中间值的问题的时候需要把产生环去掉
            String mid = getMid(first);
            System.out.println("中间值为："+mid);
        }
        /**
         * 查找中间值问题
         *      * @param first 链表的首结点
         *      * @return  链表的中间结点的值
         */
        public static String getMid(Node first){
            //定义两个指针
           Node fast = first;//快指针，是slow指针的二倍速度
           Node slow = first;//慢指针
            //使用两个指针遍历链表，当快指针指向的结点没有下一个结点，就可以结束了
            while (fast != null && fast.next != null){
                fast = fast.next.next;
                slow = slow.next;
            }
            return slow.item;
        }
        //结点类
        public static class Node{
            //存储数据
           T item;
            //下一个结点
            Node next;
            //构造函数
            Node(T item,Node next){
                this.item = item;
                this.next = next;
            }
        }
    }

  单向链表是否有环问题

  使用快慢指针的思想，还是把链表比作一条跑道，链表中有环，那么这条跑道就是一条圆环跑道，在一条圆环跑道中链表中环的入口结点，两个人有速度差，那么迟早两个人会相遇链表中环的入口结点，只要相遇就说明有环。

  代码入下：

   package cn.itcast.demo.day02.Demo02;

    public class FastSlowTest {
        public static void main(String[] args) {
            Node first = new Node("aa", null);
            Node second = new Node("bb", null);
            Node third = new Node("cc", null);
            Node fourth = new Node("dd", null);//
            Node fifth = new Node("ee", null);
            Node sixth = new Node("ff", null);
            Node seventh = new Node("gg", null);
            //完成结点之间的指向
            first.next = second;
            second.next = third;
            third.next = fourth;
            fourth.next = fifth;
            fifth.next = sixth;
            sixth.next = seventh;
            //产生环
            seventh.next = third;
        
            //判断是否有环
            boolean circle = isCircle(first);
            System.out.println("first链表中是否有环："+circle);
        }
         /* 判断链表中是否有环
         * @param first 链表首结点
         * @return true为有环，false为无环
         */
        public static boolean isCircle(Node first){
            //定义快慢指针
            Node fast = first;
            Node slow = first;
            //遍历链表，如果快慢指针指向了同一个结点，则证明有环
            while (fast != null && fast.next != null){
                fast = fast.next.next;
                slow = slow.next;
                if(fast.equals(slow)){
                    return true;
                }
            }
            return false;
        }
        //结点类
        public static class Node{
            //存储数据
           T item;
            //下一个结点
            Node next;
            //构造函数
            Node(T item,Node next){
                this.item = item;
                this.next = next;
            }
        }
    }

  有环链表入口问题

  理论：当快慢指针相遇时候，我们可以判断到链表中有环，这时重新设定一个新指针指向链表的起点，且步长与慢指针一样为1，则慢指针与“新”指针相遇的地方就是环的入口。

  代码实现入下：

   package cn.itcast.demo.day02.Demo02;

    public class FastSlowTest {
        public static void main(String[] args) {
            Node first = new Node("aa", null);
            Node second = new Node("bb", null);
            Node third = new Node("cc", null);
            Node fourth = new Node("dd", null);//
            Node fifth = new Node("ee", null);
            Node sixth = new Node("ff", null);
            Node seventh = new Node("gg", null);
            //完成结点之间的指向
            first.next = second;
            second.next = third;
            third.next = fourth;
            fourth.next = fifth;
            fifth.next = sixth;
            sixth.next = seventh;
            //产生环
            seventh.next = third;
            Node entrance = getEntrance(first);
            System.out.println("first链表中环的入口元素为："+entrance.item);
        }
        /**
         * 查找有环链表中环的入口结点
         * @param first 链表首结点
         * @return 环的入口结点
         */
        public static Node getEntrance(Node first){
            //定义快慢指针
            Node fast = first;
            Node slow = first;
            Node temp = null;
            //遍历链表，先找到环（快慢指针相遇），准备一个临时指针，指向链表的首结点
            //继续遍历，知道慢指针和临时指针相遇，那么相遇是所指向的结点就是环的入口
            while (fast != null && fast.next != null){
                //变换快慢指针
                fast = fast.next.next;
                slow = slow.next;
                //判断快慢指针是否相遇
                if(fast.equals(slow)){
                    temp = first;
                    continue;
                }
                //让临时结点变换
                if(temp != null){
                    temp = temp.next;
                    //判断临时指针是否和慢指针重合
                    if(temp.equals(slow)){
                        break;
                    }
                }
            }
            return temp;
        }
        public static class Node{
            //存储数据
           T item;
            //下一个结点
            Node next;
            //构造函数
            Node(T item,Node next){
                this.item = item;
                this.next = next;
            }
        }
    }