判断一个单链表是否存在环型链接并找出环的开始节点

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

　　最容易想到的是如果存在环那么遍历链表将会是死循环，程序无法正常退出，那么可以在遍历的时候把遍历过的节点放入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

秒客网

判断一个单链表是否存在环型链接并找出环的开始节点

相关文章