今天和同事聊天，聊到一个过往的面试题，如何判断一个单链表是否存在环，若存在输出起始节点？

　　最容易想到的是如果存在环那么遍历链表将会是死循环，程序无法正常退出，那么可以在遍历的时候把遍历过的节点放入hashset，每次检查新节点是否在set中出现过，若出现过则说明存在环。此方法看起来是能解决问题，但是存在比较大的问题 1：空间复杂度过大  2:  比较低效。

　　不妨假想一下，如果存在环，那我们用两个不同速率的指针从头开始走，这两个指针一定会相遇；如果快指针的next为null则说明不存在环，思路很简单，验证代码如下

Node类定义

 1 class Node{
 2     
 3     int val;
 4     Node next;
 5 
 6     public Node(int val){
 7         this.val = val;
 8     }
 9     
10     public String toString(){
11         return val+"";
12     }
13     
14 }

View Code

 

判断逻辑

 1 public  static boolean isHaveRing(Node node ){
 2     if(node == null || node.next == null){
 3         return false;
 4     }
 5     
 6     Node p =node;
 7     Node q = node;
 8     
 9     while( q.next != null){
10         p = p.next;
11         q = q.next.next;
12         if(p.equals(q)){
13             return true;
14         }
15     }
16     return false;
17 }
18 
19

View Code

 

　　至此，可以轻松判断一个链表是否存在环。 延伸一下那么环的起点在哪呢，这个问题乍看比较复杂，那么先画个图分析一下

 

 

n为链表长度，P为快慢指针相遇的节点，C为环的起点；头节点到C点的距离为X， C节点到P节点距离为Y

下面仔细想一下当上文的慢指针和快指针相遇时发生了什么，慢指针总共走了X ＋ Y ＝ Z步； 而快指针走了 X＋Y ＋ K*L = 2*Z步；L为环的周长，K表示若干圈

通过上面两个等式可以得到 X＋Y ＝ K＊L； 发现了什么没有？X＋Y是慢指针到相遇的节点的步数，K＊L是环周长的倍数（K为整数）如果此时一个指针Pointer从头部重新移动每次移动一步，另外一个指针从P节点移动每次也是移动一步，那么这两个节点一定会在P点相遇。而在这一段美妙旅程当中两个指针移动节奏一致，那么他们相伴而行的旅程应该是从C节点一直到P节点这一整段公共区域，也就是说当pointer一进入环他们就相遇了。从而可知，他们当他们首次相遇的节点即是环的起点。

有了以上理论指导，写出代码顺利成章了

 1 public class TestCircle {
 2 
 3     public static boolean isHaveRing(Node node) {
 4         if (node == null || node.next == null) {
 5             return false;
 6         }
 7 
 8         Node p = node;
 9         Node q = node;
10 
11         while (q.next != null) {
12             p = p.next;
13             q = q.next.next;
14             if (p.equals(q)) {
15                 return true;
16             }
17         }
18 
19         return false;
20     }
21 
22     /**
23      * 获取首次相遇时，P指针的移动步数
24      * 
25      * @param node
26      * @return
27      */
28     public static int getStep(Node node) {
29         if (node == null || node.next == null) {
30             return -1;
31         }
32         Node p = node;
33         Node q = node;
34         int pStep = 0;
35 
36         while (q.next != null) {
37             p = p.next;
38             q = q.next.next;
39             pStep++;
40             if (p.equals(q)) {
41                 return pStep;
42             }
43         }
44         return -1;
45     }
46 
47     public static int getCross(Node node, int n) {
48 
49         Node p = node;
50         Node q = node;
51         int i = 0;
52         while (p.next != null) {
53             if (n > i++) {
54                 p = p.next;
55                 continue;
56             }
57             p = p.next;
58             q = q.next;
59 
60             if (p.equals(q)) {
61                 return p.val;
62             }
63         }
64 
65         return -1;
66     }
67 
68     public static void main(String[] args) {
69         Node n1 = new Node(1);
70         Node n2 = new Node(2);
71         Node n3 = new Node(3);
72         Node n4 = new Node(4);
73         Node n5 = new Node(5);
74 
75         n1.next = n2;
76         n2.next = n3;
77         n3.next = n4;
78         n4.next = n5;
79         n5.next = n2;
80         // 慢指针走的步数
81         int n = getStep(n1);
82 
83         System.out.println(n);
84 
85         int val = getCross(n1, n);
86 
87         System.out.println(val);
88     }
89 
90 }

View Code

 

版权声明：本文为ballas原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/ballas/p/8963075.html