面试题：判断链表是否存在环

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

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

 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         }