链表例题5:查找出有环链表的环起点

佚名 5年前 (2019-01-01) 算法 745人围观抢沙发百度已收录

　　主要的方法是使用快慢指针来解决，然后让快慢指针同时向前进(让慢指针一次移动一步,快指针一次移动两步)，当慢指针移动k下时指向了环路的开头，此时快指针已经在环路中移动了k下了,设环路有L个结点这么长,那么快指针与慢指针相距为L-k的路径长度。因为都已经进入了环路内,现在就是快指针追慢指针了，慢指针一次移动一步，快指针一次移动两步，通过计算，当移动L-k次后，两指针相遇了，同时两指针距环路的开关也只有k步，所以再然头指针与慢指针同时移动，当它们相等时，即它们指向的就是环路的头结点了。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

示例图如下：

接下来移动L-k次后

代码如下：

 1 //结点类
 2 class Node{
 3     int data;
 4     Node next;
 5     public Node() {}
 6     public Node(int data) {
 7         this.data=data;
 8     }
 9 }
10 
11 public class CircleLinkedList {
12     
13 
14     public static void main(String[] args) {
15         Node node=new Node(1);
16         node.next=new Node(2);
17         node.next.next=new Node(3);
18         node.next.next.next=new Node(4);
19         node.next.next.next.next=new Node(5);
20         node.next.next.next.next.next=new Node(6);
21         node.next.next.next.next.next=node.next.next;
22         
23         if(hasCircle(node))
24         System.out.println(beginOfCirCle(node).data);
25     }
26     
27     //判断是否为有环链表
28     public static boolean hasCircle(Node head)
29     {
30         Node s=head;
31         Node f=head;
32         while(true) {
33             s=s.next;
34             f=f.next.next;
35             if(s==f) 
36                 return true;
37             if(f==null||f.next==null)
38                 return false;
39         }
40         
41         
42     }
43     
44     //查询环的开关结点
45     public static Node beginOfCirCle(Node head) {
46         Node s=head;  //慢指针
47         Node f=head;  //快指针
48         while(true) {
49             s=s.next;
50             f=f.next.next;
51             if(s==f) 
52                 break;
53         }
54         Node p=head;
55         while(p!=s) {
56             p=p.next;
57             s=s.next;
58         }
59         return p;
60     }
61 
62 }