今天和同事聊天，聊到一个过往的面试题，如何判断一个单链表是否存在环，若存在输出起始节点？
最容易想到的是如果存在环那么遍历链表将会是死循环，程序无法正常退出，那么可以在遍历的时候把遍历过的节点放入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 }
判断逻辑
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
至此，可以轻松判断一个链表是否存在环。 延伸一下那么环的起点在哪呢，这个问题乍看比较复杂，那么先画个图分析一下
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 }