【数据结构】给定一个链表，判定链表是否有环，如果有，返回链表开始入环的第一个节点， 如果链表无环，则返回 null。

1.判断链表是否有环

思路：使用快慢指针解决是否有环

假设链表是一个有环链表，设置两个指针，slow，和fast让两个指针从前往后遍历，而且fast的遍历速度是slow的两倍，如果有环的话，遍历快的fast的不会为null，并且slow一定会追上fast，fast会和slow相等，过程如下图所示：fast走两步，slow走一步

                            

代码：

 public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(slow != null && fast != null){
            fast = fast.next;
            if(fast != null){
                fast = fast.next;
                slow = slow.next;
            }
            if(fast == slow){
                return true;
            }
        }
        return false;
    }

2.求出成环的位置

思路：s=vt（路程 = 速度 * 时间），用方程思想列等式解

因为路程知道，速度知道（二倍关系），时间也知道（相等），可以列等式关系进行求解；

如下图：假设链表是Link，fast是快的指针，slow是慢的指针；

k是环的入口，p是快慢指针相遇的地方；a，b，c分别代表三段长度；

         

所以，让指针从相遇点p和起始点同时遍历，这样由于c = a所以p1和p2在k相遇，而k就是入口；

          

代码如下：

 public static ListNode detectCycle(ListNode head){
        if(head == null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        do{
            fast = fast.next;
            if(fast != null){
                fast = fast.next;
                slow = slow.next;
            }
        }while(fast != null && fast != slow);
        if(fast == null){
            return null;
        }
        ListNode p1 = head;
        ListNode p2 = slow;
        while(p1 != p2){
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }

 

参考文章：https://blog.csdn.net/weixin_40879743/article/details/90646399