快慢指针

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

1.中间值问题

//结点类
private static class Node<T> {
    //存储数据
    T item;
    //下一个结点
    Node next;
    public Node(T item, Node next) {
        this.item = item;
        this.next = next;
    }
}
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);
}
/**
     * 获取中间值
     *
     * @param first 链表的首结点
     * @return 链表的中间结点的值
     */
public static String getMid(Node<String> first) {
    return null;
}

获取中间值方法

利用快慢指针，我们把一个链表看成一个跑道，假设a的速度是b的两倍，那么当a跑完全程后，b刚好跑一半，以此来达到找到中间节点的目的。

如下图，最开始，slow与fast指针都指向链表第一个节点，然后slow每次移动一个指针，fast每次移动两个指针。

public static String getMid(Node<String> first) {
    Node<String> fast = first;
    Node<String> slow = first;
    //当块结点走到头结束
    while (fast.next != null) {
        //慢结点一次走一个next
        slow = slow.next;
        //快结点一次走两个next，速度是slow的两倍
        fast = fast.next.next;
    }
    return slow.item;
}

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

public class FastSlowLinkList {   
    //结点类
    private static class Node<T> {
        //存储数据
        T item;
        //下一个结点
        Node next;

        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
    public static void main(String[] args) {
        //创建结点
        Node<String> first = new Node<>("aa", null);
        Node<String> second = new Node<>("bb", null);
        Node<String> third = new Node<>("cc", null);
        Node<String> fourth = new Node<>("dd", null);
        Node<String> fifth = new Node<>("ee", null);
        Node<String> six = new Node<>("ff", null);
        Node<String> seven = new Node<>("gg", null);
        //完成结点之间的指向
        first.next = second;
        second.next = third;
        third.next = fourth;
        fourth.next = fifth;
        fifth.next = six;
        six.next = seven;
        //造成环路
        seven.next=fourth;
        //判断链表是否有环
        boolean circle = isCircle(first);
        System.out.println("first链表中是否有环：" + circle);
    }
    /**
     * 判断链表中是否有环
     *
     * @param first 链表首结点
     * @return ture为有环，false为无环
     */
    public static boolean isCircle(Node<String> first) {
        return false;
    }
}

判断是否有环

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

/**
     * 判断链表中是否有环
     *
     * @param first 链表首结点
     * @return ture为有环，false为无环
     */
public static boolean isCircle(Node<String> first) {
    Node<String> fast = first;
    Node<String> slow = first;
    //快结点或者慢结点指向为null，这肯定不是
    while (fast.next!=null&&slow.next!=null){
        //慢结点一次走一个next
        slow = slow.next;
        //快结点一次走两个next，速度是slow的两倍
        fast = fast.next.next;
        if (slow.equals(fast)){
            return true;
        }
    }
    return false;
}

这里可以自行更改是否构成回路，进行测试

3.有环链表入口问题

public class FastSlowLinkList {
    //结点类
    private static class Node<T> {
        //存储数据
        T item;
        //下一个结点
        Node next;
        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
    public static void main(String[] args) {
        //创建结点
        Node<String> first = new Node<>("aa", null);
        Node<String> second = new Node<>("bb", null);
        Node<String> third = new Node<>("cc", null);
        Node<String> fourth = new Node<>("dd", null);
        Node<String> fifth = new Node<>("ee", null);
        Node<String> six = new Node<>("ff", null);
        Node<String> seven = new Node<>("gg", null);
        //完成结点之间的指向
        first.next = second;
        second.next = third;
        third.next = fourth;
        fourth.next = fifth;
        fifth.next = six;
        six.next = seven;
        //造成环路
        seven.next = fourth;
        //查找环的入口结点
        Node<String> entrance = getEntrance(first);
        System.out.println("链表中环的入口结点元素为：" + entrance.item);
    }
    /**
     * 查找有环链表中环的入口结点
     *
     * @param first 链表首结点
     * @return 环的入口结点
     */
    public static Node getEntrance(Node<String> first) {
        return null;
    }
}

解决环入口问题

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

/**
     * 查找有环链表中环的入口结点
     *
     * @param first 链表首结点
     * @return 环的入口结点
     */
public static Node getEntrance(Node<String> first) {
    Node<String> fast = first;
    Node<String> slow = first;
    Node<String> nNode = first;
    while (fast.next != null && slow.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        //此时有环
        if (slow.equals(fast)) {
            while (!nNode.equals(slow)) {
                nNode = nNode.next;
                slow = slow.next;
            }
            break;
        }
    }
    return nNode;
}

这里可以自行更改构成环路的入口位置，多次实验