算法7— 判断一个单链表是否有环，如果有，找出环的起始位置

本文主要是介绍算法7— 判断一个单链表是否有环，如果有，找出环的起始位置，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第一种方法是从单链表head开始，每遍历一个，就把那个node放在hashset里，走到下一个的时候，把该node放在hashset里查找，如果有相同的，就表示有环，如果走到单链表最后一个node，在hashset里都没有重复的node，就表示没有环。这种方法需要O(n)的空间和时间。

第二种方法是设置两个指针指向单链表的head, 然后开始遍历，第一个指针走一步，第二个指针走两步，如果没有环，它们会直接走到底，如果有环，这两个指针一定会相遇。

[java]  view plain copy  
 public boolean hasLoop(Node head) {  
     if (head == null) return false;  
     //slow pointer  
     Node sPointer = head.next();      
     if (sPointer == null) return false;  
     //fast pointer  
     Node fPointer = sPointer.next();      
     while (sPointer != null && fPointer != null) {  
         if (sPointer == fPointer) return true;    
         sPointer = sPointer.next();   
         fPointer = fPointer.next();   
         if (fPointer != null) {  
             fPointer = fPointer.next();  
         }  
     }  
         return false;  
 }  

当我们知道这个链表有环了，那么找出起始位置就比较简单。

[java]  view plain copy  
 /* (Step 1) Find the meeting point. This algorithm moves two pointers at 
 * different speeds: one moves forward by 1 node, the other by 2. They 
 * must meet (why? Think about two cars driving on a track—the faster car 
 * will always pass the slower one!). If the loop starts k nodes after the 
 * start of the list, they will meet at k nodes from the start of the 
 * loop. */  
 n1 = n2 = head;  
 while (TRUE) {  
     n1 = n1->next;  
     n2 = n2->next->next;  
     if (n1 == n2) {  
         break;  
     }  
 }  
 // Find the start of the loop.  
 n1 = head;  
 while (n1 != n2) {  
     n1 = n1->next;  
     n2 = n2->next;  
 }  
 Now n2 points to the start of the loop.  

分析：上面的代码为何能够找到环的起始位置？

假设环的长度是 m, 进入环前经历的node的个数是 k , 那么，假设经过了时间 t，那么速度为2 的指针距离起始点的位置是: k + (2t - k) % m = k + (2t - k) - xm . 同理，速度为1的指针距离起始点的位置是 k + (t - k) % m = k + (t - k) - ym。

如果 k + (2t - k) - xm = k + (t - k) - ym ，可以得到 t = m (x - y)。那么当t 最小为m的时候，也就是说，两个指针相聚在距离起始点 m - k的环内。换句话说，如果把一个指针移到链表的头部，然后两个指针都以 1 的速度前进，那么它们经过 k 时间后，就可以在环的起始点相遇。

这篇关于算法7— 判断一个单链表是否有环，如果有，找出环的起始位置的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！