判断链表是否有环

有一个单向链表，链表中有可能出现“环”，就像下图这样。那么，如何用程序来判断该链表是否为有环链表呢？

方法1

创建一个以节点ID为Key的HashSet集合，用来存储曾经遍历过的节点。然后同样从头节点开始，依次遍历单链表中的每一个节点。每遍历一个新节点，都用新节点和HashSet集合中存储的节点进行比较，如果发现HashSet中存在与之相同的节点ID，则说明链表有环，如果HashSet中不存在与新节点相同的节点ID，就把这个新节点ID存入HashSet中，之后进入下一节点，继续重复刚才的操作。

遍历过5，3

遍历过过5、3、7、2、6、8、1

当再一次遍历节点2时，查找HashSet，发现节点已存在。

由此可知，链表有环。

时间复杂度是O(n)。
空间复杂度：O(n)。（使用了额外的存储空间）

方法2

利用指针
首先创建两个指针p1和p2（在Java里就是两个对象引用），让它们同时指向这
个链表的头节点。然后开始一个大循环，在循环体中，让指针p1每次向后移动1个节
点，让指针p2每次向后移动2个节点，然后比较两个指针指向的节点是否相同。如果
相同，则可以判断出链表有环，如果不同，则继续下一次循环。

此方法就类似于一个追及问题。

该算法的时间复杂度为O(n)。除两个指针外，没有使用任何额外的存储空间，所以空间复杂度是O(1)

JAVA实现

package algorithmProblem;
//判断链表是否有环




public class isCycle {
    
      

    /**
     * 链表节点
     */
    private static class Node{
    
      
        int data;
        Node next;

        public Node(int data) {
    
      
            this.data = data;
        }
    }

    /**
     * 判断是否有环
     * @param head 链表头节点
     * @return
     */
    public static boolean isCycle1(Node head){
    
      
        //建立俩个快慢指针
        Node p1 = head;//慢
        Node p2 = head;//快
        while (p2!=null&&p2.next!=null){
    
      
            p1 = p1.next;
            p2 = p2.next.next;
            if(p1==p2){
    
      
                //成功追及，有环
                return true;
            }
        }
        //没有环
        return false;
    }

    public static void main(String[] args) throws Exception{
    
      
        Node node1=  new Node(5);
        Node node2=  new Node(3);
        Node node3=  new Node(7);
        Node node4=  new Node(2);
        Node node5=  new Node(6);
        Node node6=  new Node(8);
        Node node7=  new Node(1);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        node7.next = node4;//这里就上环了
        System.out.println("链表是否有环： "+isCycle1(node1));

    }
}

问题扩展1

如果链表有环，如何求出环的长度？

环长 = 每一次速度差 × 前进次数 = 前进次数。

指针p1每次走1步，指针p2每次走2步，两者的速度差是1步。当两个指针再次相遇时，p2比p1多走了整整1圈。

package algorithmProblem;
//求环长
public class isCycle2 {
    
      

    /**
     * 链表节点
     */
    private static class Node{
    
      
        int data;
        isCycle2.Node next;

        public Node(int data) {
    
      
            this.data = data;
        }
    }

    /**
     * 判断是否有环
     * @param head 链表头节点
     * @return
     */
    public static boolean isCycle1(isCycle2.Node head){
    
      
        //建立俩个快慢指针
        isCycle2.Node p1 = head;//慢
        isCycle2.Node p2 = head;//快
        while (p2!=null&&p2.next!=null){
    
      
            p1 = p1.next;
            p2 = p2.next.next;
            if(p1==p2){
    
      
                //成功追及，有环
                return true;
            }
        }
        //没有环
        return false;
    }

    //在有环的情况下，求环长
    public static int lenCycle(isCycle2.Node head){
    
      
        //建立俩个快慢指针
        isCycle2.Node p1 = head;//慢
        isCycle2.Node p2 = head;//快
        //记录追及后的步数
        int pos=0;
        //记录追及的次数
        int time=0;
        //记录环的长度
        int len = 0;
        while (p2!=null&&p2.next!=null){
    
      
            p1 = p1.next;
            p2 = p2.next.next;
            if (p1==p2){
    
      
                System.out.println("追及");
                //第一次追上后把pos置零，开始计算追上后过了多少步，再次追上
                if(time==0){
    
      
                    pos=0;
                }
                time++;
                if(time==2){
    
      
                    break;
                }
            }
            pos++;

        }
        len = (2-1)*pos;
        return len;
    }

    public static void main(String[] args) throws Exception{
    
      
        isCycle2.Node node1=  new isCycle2.Node(5);
        isCycle2.Node node2=  new isCycle2.Node(3);
        isCycle2.Node node3=  new isCycle2.Node(7);
        isCycle2.Node node4=  new isCycle2.Node(2);
        isCycle2.Node node5=  new isCycle2.Node(6);
        isCycle2.Node node6=  new isCycle2.Node(8);
        isCycle2.Node node7=  new isCycle2.Node(1);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        node7.next = node4;//这里就上环了
        System.out.println("链表是否有环： "+isCycle1(node1));
        if(isCycle1(node1)){
    
      
            System.out.println("环长为： "+lenCycle(node1));
        }

        //System.out.println(node7.next.next.next.next.next.next.data);

    }
}

问题扩展2

如果链表有环，如何求出入环节点？

package algorithmProblem;
//求环长
public class isCycle2 {
    
      

    /**
     * 链表节点
     */
    private static class Node{
    
      
        int data;
        isCycle2.Node next;

        public Node(int data) {
    
      
            this.data = data;
        }
    }

    /**
     * 判断是否有环
     * @param head 链表头节点
     * @return
     */
    public static boolean isCycle1(isCycle2.Node head){
    
      
        //建立俩个快慢指针
        isCycle2.Node p1 = head;//慢
        isCycle2.Node p2 = head;//快
        while (p2!=null&&p2.next!=null){
    
      
            p1 = p1.next;
            p2 = p2.next.next;
            if(p1==p2){
    
      
                //成功追及，有环
                return true;
            }
        }
        //没有环
        return false;
    }

    //在有环的情况下，求环长
    public static int lenCycle(isCycle2.Node head){
    
      
        //建立俩个快慢指针
        isCycle2.Node p1 = head;//慢
        isCycle2.Node p2 = head;//快
        //记录追及后的步数
        int pos=0;
        //记录追及的次数
        int time=0;
        //记录环的长度
        int len = 0;
        while (p2!=null&&p2.next!=null){
    
      
            p1 = p1.next;
            p2 = p2.next.next;
            if (p1==p2){
    
      
                System.out.println("追及");
                if(time==0){
    
      
                    pos=0;
                }
                time++;
                if(time==2){
    
      
                    break;
                }
            }
            pos++;

        }
        len = (2-1)*pos;
        return len;
    }

    //求首次相遇点
    //在有环的情况下，求首次相遇点
    public static Node firstMeet(isCycle2.Node head){
    
      
        //建立俩个快慢指针
        isCycle2.Node p1 = head;//慢
        isCycle2.Node p2 = head;//快
        while (p2!=null&&p2.next!=null){
    
      
            p1 = p1.next;
            p2 = p2.next.next;
            if (p1==p2){
    
      
                System.out.println("首次相遇");
                return p1;
            }


        }
    return null;
    }

    /**
     * 求入环点
     * @param head      头指针
     * @param firstmeet 首次相遇点指针
     * @return
     */
    public static int intoPosition(isCycle2.Node head ,isCycle2.Node firstmeet){
    
      
        int len=0;
        while (head!=firstmeet){
    
      
            head=head.next;
            firstmeet =firstmeet.next;
            len++;

        }
        return len;
    }
    public static void main(String[] args) throws Exception{
    
      
        isCycle2.Node node1=  new isCycle2.Node(5);
        isCycle2.Node node2=  new isCycle2.Node(3);
        isCycle2.Node node3=  new isCycle2.Node(7);
        isCycle2.Node node4=  new isCycle2.Node(2);
        isCycle2.Node node5=  new isCycle2.Node(6);
        isCycle2.Node node6=  new isCycle2.Node(8);
        isCycle2.Node node7=  new isCycle2.Node(1);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        node7.next = node4;//这里就上环了
        System.out.println("链表是否有环： "+isCycle1(node1));
        if(isCycle1(node1)){
    
      
            System.out.println("环长为： "+lenCycle(node1));
        }
        if(isCycle1(node1)){
    
      
            System.out.println("首次相遇点距离头节点： "+intoPosition(node1,firstMeet(node1)));
        }


        //System.out.println(node7.next.next.next.next.next.next.data);

    }
}