1 package com.interview;  2   3 public class _7_1JudgeListCycle {  4   5     /**  6      * @param args  7      */  8     public static int x=0, y=0, k=0;   //分别记录圈外链表的长度,圈的长度,第一次相遇时慢指针走的总长度  9     public static void main(String[] args) { 10         Node first = createList(24, 6);   //创建有环链表 11         judge(first);      //判断该单链表是否有环 12     } 13      14     //创建带头节点的链表、参数为：链表总长度，入口节点 15     public static Node createList(int size, int entry){ 16         /**  1)用尾插法构建单链表，此处构建有环单链表，让node24指向node6*/ 17         Node first = new Node(null,null);    //头节点 18         Node r = first;   //指向链表的尾节点 19         Node t = null;    //指向环的入口节点 20         for(int i=1;i<=size;i++){ 21             Node node = new Node((new Stu(""+i,"小牛犊@"+i)),null); 22             r.next = node; 23             r = node; 24             if(i==entry) t = r;  //让环的入口为节点6 25         } 26         r.next = t;       //若是构建无环单链表，此处   r.next = null; 27         return first; 28     } 29      30     //判断是否有环 31     public static void judge(Node first){ 32         /**  2)判断是否有环若pq先重合则有环，若q先指向null,则无环    */ 33         Node p = first.next; 34         Node q = first.next; 35         String flag = "0";  //标记有环还是无环,0-无环,1-有环 36         if(p==null){     //空链表 37             System.out.println("链表为空！"); 38             return; 39         } 40         k = 1; 41         while(q.next!=null && q.next.next!=null){ 42             k++;       43             p=p.next; 44             q=(q.next).next; 45             if(q.equals(p)){ 46                 flag="1"; 47                 System.out.println("p和q相遇了,该单链表有环！"); 48                 break; 49             } 50         } 51          52         /**  3)有环的时候求环的入口节点    */ 53         if(flag.equals("1")){    //有环 54             p=first.next; //p重新指向第一个节点 55             searchEnter(p,q); 56         } 57         else{   //是因为q走到了尽头才跳出循环的，无环 58             System.out.println("该单链表没有环！"); 59         } 60     } 61      62     //求环的入口节点     63     public static void searchEnter(Node p, Node q){ 64         x=1; 65         while(!q.equals(p)){ 66             x++;  //求圈外长度 67             p=p.next; 68             q=q.next; 69         } 70         Node r = q.next;   //为了求圈长设定的 71         y = 1;     //求圈长度 72         while(r!=q){ 73             r = r.next; 74             y++; 75         } 76          77         System.out.println("入口节点是链表中的第"+ x+"个节点！"); 78         System.out.println("入口节点的no: "+ p.stu.no); 79         System.out.println("入口节点的名字为: "+ p.stu.name); 80         System.out.println("圈的长度是："+ y); 81         System.out.println("第一次相遇时，慢指针在圈内走的长度为："+ (k-x)); 82         System.out.println("第一次相遇时，快指针在圈内走了："+ (k/y)+"圈"); 83         System.out.println("第二次相遇时，快指针在圈内又走了："+ (k/y-1)+"圈"); 84     } 85      86     //链表节点的数据结构 87     static class Node { 88         public Stu stu; 89         public Node next; 90          91         public Node() { 92             super(); 93             // TODO Auto-generated constructor stub 94         } 95         public Node(Stu stu, Node next) { 96             super(); 97             this.stu = stu; 98             this.next = next; 99         }100     }101     102     //节点立里的元素103     private static class Stu {104         public String no;105         public String name;106         public Stu(String no, String name) {107             super();108             this.no = no;109             this.name = name;110         }111     }112 }