题目：判断链表是否存在环

思路：定义快慢指针，如果两个指针相遇则一定存在环。

1    public bool IsCircled(Node First) 2         { 3             if (First == null || First.Next == null) 4             { 5                 return false; 6             } 7             else 8             { 9                 Node slow = First;10                 Node fast = First;11                 while (fast != null && fast.Next != null)12                 {13                     fast = fast.Next.Next;14                     slow = slow.Next;15                     if (slow == fast)16                     {17                         break;18                     }19 20                 }21                 if (fast == null || fast.Next == null)22                 {23                     return false;24                 }25                 else return true;26             }27         }

拓展1

求环的长度：

思路：从快慢指针第一次相遇开始计数，再次相遇时停止计数。

1   public int GetloopLength(Node First) 2         { 3             if (First == null && First.Next == null) return 0; 4             else 5             { 6                 Node slow = First; 7                 Node fast = First; 8                 int length = 0; 9                 bool start = false;10                 bool again = false;11                 while (fast != null && fast.Next != null)12                 {13                     fast = fast.Next.Next;14                     slow = slow.Next;15                     if (fast == slow && again == true)16                     {17                         break;18                     }19                     if (fast == slow && again == false)20                     {21                         start = true;22                         again = true;23                     }24                     if (start == true)25                     {26                         length++;27                     }28                 }29                 return length;30             }31         }

拓展2 

求环的入口：

思路：头结点到入口点的距离=链表总长-环长

1  public Node FindLoopEntrance(Node First) 2         { 3             if (First == null || First.Next == null) return null; 4             else 5             { 6                 int sumLength = 0; 7                 int loopLength = 0; 8                 Node slow = First; 9                 Node fast = First;10                 bool start = false;11                 bool again = false;12 13                 while (fast != null && fast.Next != null)14                 {15                     fast = fast.Next.Next;16                     slow = slow.Next;17                     if (fast == slow && again == true) break;18                     if (fast == slow && again == false)19                     {20                         start = true;21                         again = true;22                     }23                     if (start == true) loopLength++;24                     sumLength++;25                 }26                 int indexOfEntrance = sumLength - 2 * loopLength;27                 int i = 0;28                 Node entrance = First;29                 while (entrance.Next != null)30                 {31                     if (indexOfEntrance == i) break;32                     entrance = entrance.Next;33                     i++;34                 }35                 return entrance;36             }37         }