本文共 711 字，大约阅读时间需要 2 分钟。

题目：如何判断一个单链表是否有环？有环的话返回进入环的第一个节点的值，无环的话返回-1。如果链表的长度为N，请做到时间复杂度O(N)，额外空间复杂度O(1)。

给定一个单链表的头结点head（注意另一个参数adjust为加密后的数据调整参数，方便数据设置，与本题求解无关)，请返回所求值。

详见LB7，只是返回值不同，是返回结点值或者-1。

普通方法，空间复杂度为O(1)，使用hash表，将每个遍历的对象放入到hash中，然后逐个向下遍历，每遍历一个去hash表中寻找有无相同的对象；如果有就说明循环，即有环；注意，只要有环，总是能够遍历有相同的对象，环不可能无限大。如果pcur==null那么显然无环。

public class ChkLoop {     public int chkLoop(ListNode head, int adjust)    {        //特殊的输入        if (head==null) return -1;        //计算得到环中结点的数目        int nodesNumberOfLoop=this.NodesNumberOfLoop(head);        //如果没有环，直接返回null        if(nodesNumberOfLoop==0) return -1;                //如果有环，并且已知环的结点数目为n，来找环的入口结点        ListNode p1=head;        ListNode p2=head;        //指针p1先走n步        for(int i=0;i

转载地址：http://pvzin.baihongyu.com/