题解 | #判断链表中是否有环#

import java.util.*;
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        //使用两个指针指向入环节点和出环节点
        if (head == null) return false;
        ListNode inNode,outNode;
        inNode = head;
        outNode = inNode.next;
        while (outNode != null){
            if (outNode.next == null) return false;
            if (outNode.next == inNode) return true;
            //System.out.println(outNode.val);
            //System.out.println(inNode.val);
            inNode = inNode.next;
            outNode = outNode.next;
            if (outNode.next == null) return false;
		  	if (outNode.next == inNode) return true;
            outNode = outNode.next;

        }
        return false;
    }
}

这里使用的是双指针，一个快指针一个慢指针，快指针每次移动两个位置，慢指针每次移动一个位置，如果有环，快慢指针会重合。使用这样的一对快慢指针，每一次循环，快指针和慢指针之间的距离都会+1。当快慢指针重合时，说明环的长度等于快慢指针之间距离的约数。

为什么有环情况下 快慢 指针会重合？这个问题应该可以转换成一个数学问题。

假设快指针在链表中下标为fastIndex，慢指针在链表中下标为slowIndex：

初始都为0，但fastIndex每次+2，slowIndex每次+1，所以fastIndex = 2 * slowIndex；

有环情况下，假设环长度为n，链表中，环前节点个数为preNum，当循环 i 次时，

快指针移动了 2i, 而fastIndex = （2i-preNum）% n + preNum；

慢指针移动了 i，slowIndex = （i-preNum）% n +preNum。

有环情况下，快慢指针会重合也就意味着 存在i 使得fastIndex = slowIndex，

即（2i-preNum）% n = （i-preNum） % n

那么这样的i存在吗？

2i-preNum = tkn+b

i-preNum = kn+b

t，k是整数，b是整数且0<=b<n。消去 i 可以得到；

（t-2）kn = b+preNum；因为b+preNum>=0,所以t>=2,说明快指针至少比慢指针快一圈。

（t-2）k为整数，且>=0，而总存在b使得b+preNum为n的整数倍，

比如preNum等于0时，只需b=0，则满足b+preNum是n的0倍，这说明当链表是一个环时，两个指针会在环的起始节点汇合。

当preNum>0时，总存在整数b，0<b<n使得b+preNum是n 的整数倍，具体是多少倍需要看preNum的大小。