引言

单链表的尾环问题是一个比较经典的问题，它涉及的问题如下:
1>给一个单链表，判断其中是否有环的存在;
2>如果存在环，找出环的入口点;
3>如果存在环，求出环上节点的个数;
4>如果存在环，求出链表的长度;
5>如果存在环，求出环上距离任意一个节点最远的点(对面节点)；
6>(扩展)如何判断两个无环链表是否相交
7>(扩展）如果相交，求出第一个相交的节点.
下面在分析带环链表的特征的基础上来一一解决这些问题.

尾环链表特征分析

1.下图是尾环链表的结构。我们采用快慢指针的方法，很明显的，这是一个典型的“跑道追及问题”,俩指针进入“跑道”，速度不一样，那么俩指针必然会在某一时刻相遇。

尾环链表(摘自网络).png

因此判断链表是否有环的关键就是判断俩指针是否能相遇:

    /**
     * 判断是否有回环
     *
     * @return
     */
    public boolean isLoop() {
       if (isEmpty()) {
            return false;
        }
        SNode<T> slow = headNode;
        SNode<T> fast = headNode;
        while (slow != null && fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {//俩哥们相遇，则返回true
                return true;
            }
        }
        //如果是单链表，快指针肯定会走到结尾跳出循环
        return false;
    }

2.下面分析入口点问题。如下图:

尾环链表环入口分析(摘自网络).png
说明：a为头到入口的距离,x为入口到相遇点的距离,r为环长度,链表长度为L，设定环的位置以入口为原点，顺时针为正方向。这里为了更加清晰的说理，这里特殊到一般分两种情况分析:
1>环较大，俩指针在环内一周之内相遇:当slow到达入口时，fast走了2a,在环内的位置为2a-a = a,此时fast在环上顺时针领先slow距离为a，相应的slow在环上顺时针"领先"fast的距离为r-a,因为每一步fast都比slow快一步，所以再经过r-a步，fast就可以追上slow了，此时相遇时，slow共走了a+(r-a)=r步，那么在环的位置为r-a,此时有相遇点到入口的顺时针距离正好为a，与头结点到入口的距离相等;
2>环较小，快指针已经在环里浪了n(n>=1)圈才与慢指针相遇:设头结点到相遇点的距离为s,那么fast走了2s,另外fast在环里转了n圈距离为(nr + s),所以有2s = s+nr得s = nr;又有a+x=s=nr,得a + x = (n-1)r + (L - a),推出a = (n-1)*r+(L-a-x);后者为环上相遇点到入口的顺时针距离.前者代表环转圈路程，这个公式表示的现实意义为:设定俩指针，一个指针p从head出发向入口运动,另外一个指针q从相遇点出发在环内顺时针运动，一定步数后一定会在入口相遇,此结论与情况1一致。
因此问题2的实现思路为:找到相遇点，然后分配指针分别从头结点和相遇点出发向前移动，如果相遇则相遇点为入口点.代码如下:

   /**
     * 查找环入口
     *
     * @return
     */
    public SNode<T> findLoopStartNode() {
      if (isEmpty()) {
            return null;
        }
        SNode<T> slow = headNode;
        SNode<T> fast = headNode;
        while (slow != null && fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {//俩哥们相遇，则返回true
                break;
            }
        }

        if (slow == null || fast == null || fast.next == null) return null;//没有环则返回空
        SNode<T> p = headNode;//从头节点出发
        SNode<T> q = slow;//从相遇点出发
        while (p != q) {
            p = p.next;
            q = q.next;
        }
        return p;//相遇点为环入口
    }

3.有了环入口,那么环大小就好说了，从相遇点开始遍历就行:

    /**
     * 获取环大小
     * @return
     */
    public int getLoopSize() {
          if (isEmpty()) {
            return 0;
        }
        SNode<T> slow = headNode;
        SNode<T> fast = headNode;
        while (slow != null && fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {//俩哥们相遇，则返回true
                break;
            }
        }

        if (slow == null || fast == null || fast.next == null) return 0;//没有环则返0
        int size = 1;//环size从1开始
        SNode<T> temp = slow.next;//从相遇点出发
        while (temp != slow) {
            size++;
            temp = temp.next;
        }
        return size;
    }

4.求环链表的长度:环链表的长度为环大小和入口到头节点距离的和:

   /**
     * 获取头节点到入口的距离
     *
     * @return
     */
    public int getLoopEntryDistance() {
        if (isEmpty()) {
            return 0;
        }
        SNode<T> slow = headNode;
        SNode<T> fast = headNode;
        while (slow != null && fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {//俩哥们相遇，则返回true
                break;
            }
        }

        if (slow == null || fast == null || fast.next == null) return size();//没有环则返回单链表长度
        SNode<T> p = headNode;//从头节点出发
        SNode<T> q = slow;//从相遇点出发
        int distance = 0;
        while (p != q) {
            distance++;
            p = p.next;
            q = q.next;
        }
        return distance;
    }

   /**
     * 获得带环链表大小
     * @return
     */
    public int getLoopLinkedListSize(){
        return getLoopSize() + getLoopEntryDistance();
    }

5.对面节点问题。环上距离节点最远的节点为对面节点，如图1和4、2和5、3和6为对面节点，且距离最大为环大小的一半。思路如下：判断节点是否在环上，如果在环上从当前节点前移环大小一半的步数.

对面节点问题.png

   /**
     * 获得对面节点
     *
     * @return
     */
    public SNode<T> getOppositeNode(SNode<T> node) {
        boolean isLoop = false;
        if (isEmpty() || node == null) {
            return null;
        }
        boolean isOnLoop = false;
        //判断节点是否在环上
        SNode<T> startNode = findLoopStartNode();
        if (startNode == null) {//没有环，返回空
            return null;
        }
        int loopSize = getLoopSize();
        for (int i = 0; i < loopSize; i++) {
            if (node == startNode) {
                isOnLoop = true;
                break;
            }
            startNode = startNode.next;
        }
        SNode<T> temp = node;
        if (isOnLoop) {
             //走环一半步数
            for (int i = 0; i < loopSize / 2; i++) {
                temp = temp.next;
            }
        }
        return temp;
    }

6.对于俩扩展问题，可以这样理解:加入链表A和B有交点，那么将其中一个链表首尾相连，那么另一个链表上必然会出现环，问题就转化成问题一，这里不在赘述。
总结:关于单链表，最核心的操作就是玩转节点的遍历、断开和连接操作，这四篇博客基本涵盖了单链表的大部分操作，为什么花费如此多的精力去学习它呢?因为它是基础，包含了节点操作的基本思想，熟悉了它，后面的双向链表、栈、队列就相对容易。当然，还是那句话：学习数据结构就是学习思想。一沙一世界，单链表也有很多东西可以发掘！关于单链表的学习暂时告一段落，如有纰漏欢迎指正！