有环链表查找环

cu_Cbear

有环链表查找环

java数据结构算法环状链表linkedlist
有环链表如何高效的判断是否有环，以及在何处产生环？

采用2个指针不同步数（步数小的每次1步，步数大的每次2步），步数大的如果能够与步数小的相遇则必然存在环。









相遇后的情况如图，假设相遇后步数大的回绕环遍历了n遍，步数小的肯定一遍也没遍历完，假设第一段距离为a，第2段距离为c，第3段距离为b

则有（a+c）*2 = a+n（b+c）+c，转换后得 a = n（b+c） - c，也就是说，从出发点出发，移动a的距离，刚好等于相遇点出发移动n个整圈减c的距离，这个点刚好就是环产生的点，由此可以设置2个指针，分别从根节点与相遇点出发，第一次相遇的地方则是环产生的点。

完成证明后，代码较为简单，如下



Java代码

1. package com.xhb.algorithms;   
   
2.   
   
3. public class MyLinkedList {   
   
4.     private LinkListNode<Integer> root = new LinkListNode<Integer>(null, null);   
   
5.     private int length;   
   
6.     private int point;   
   
7.   
   
8.     /**  
   
9.      * @param args  
   
10.      */  
    
11.     public static void main(String[] args) {   
    
12.         MyLinkedList list = new MyLinkedList(10045, 232);   
    
13.         System.out.println(list.isHasRound());   
    
14.         System.out.println("the point cut obj is " + list.getCutPoint());   
    
15.     }   
    
16.   
    
17.     /**  
    
18.      * 初始化一个环链表  
    
19.      */  
    
20.     private MyLinkedList(int length, int point) {   
    
21.         this.length = length;   
    
22.         this.point = point;   
    
23.         LinkListNode<Integer> current = this.root;   
    
24.         for (int i = 1; i <= this.length - 1; i++) {   
    
25.             current = current.next(new LinkListNode<Integer>(new Integer(i),   
    
26.                     null));   
    
27.         }   
    
28.         if (this.point < 0) {   
    
29.             current.next(null);   
    
30.         } else {   
    
31.             LinkListNode<Integer> pointObj = this.root;   
    
32.             for (int i = 0; i < point; i++) {   
    
33.                 pointObj = pointObj.next();   
    
34.             }   
    
35.             current.next(pointObj);   
    
36.         }   
    
37.     }   
    
38.   
    
39.     public Integer getCutPoint() {   
    
40.         LinkListNode<Integer> seekPoint = this.getSeekPoint();   
    
41.         System.out.println(seekPoint.data());   
    
42.         LinkListNode<Integer> a = this.root;   
    
43.         while (true) {   
    
44.             a = a.next();   
    
45.             seekPoint = seekPoint.next();   
    
46.             if (a == seekPoint) {   
    
47.                 return a.data();   
    
48.             }   
    
49.             // System.out.println(a.data() +"," + seekPoint.data());   
    
50.         }   
    
51.     }   
    
52.   
    
53.     private LinkListNode<Integer> getSeekPoint() {   
    
54.         LinkListNode<Integer> a = this.root;   
    
55.         LinkListNode<Integer> b = this.root;   
    
56.         a = a.next();   
    
57.         b = b.next().next();   
    
58.         while (true) {   
    
59.             a = a.next();   
    
60.             b = b.next();   
    
61.             if (b == null) {   
    
62.                 return null;   
    
63.             }   
    
64.             if (a == b && b != null) {   
    
65.                 return b;   
    
66.             }   
    
67.             b = b.next();   
    
68.             if (b == null) {   
    
69.                 return null;   
    
70.             }   
    
71.             if (a == b && b != null) {   
    
72.                 return b;   
    
73.             }   
    
74.         }   
    
75.     }   
    
76.   
    
77.     public boolean isHasRound() {   
    
78.         return this.getSeekPoint() != null;   
    
79.     }   
    
80. }   
    
81.   
    
82. class LinkListNode<T> {   
    
83.     private LinkListNode<T> next = null;   
    
84.     private T data;   
    
85.   
    
86.     public LinkListNode(T data, LinkListNode<T> next) {   
    
87.         this.data = data;   
    
88.         this.next = next;   
    
89.     }   
    
90.   
    
91.     public LinkListNode<T> next() {   
    
92.         return next;   
    
93.     }   
    
94.   
    
95.     public LinkListNode<T> next(LinkListNode<T> next) {   
    
96.         this.next = next;   
    
97.         return next;   
    
98.     }   
    
99.   
    
100.     public T data() {   
     
101.         return this.data;   
     
102.     }   
     
103.   
     
104.     @Override  
     
105.     public String toString() {   
     
106.         return data.toString();   

复制代码

}   
}  

芯忻相依

谢谢分享