【面试】3.如何判断链表是否有环？如何计算环的长度？

1.如何判断是否有环？如果有两个头结点 指针 ，一个走的快，一个走的慢，那么若干步以后，快的指针总会超过慢的指针一圈。

2.如何计算环的长度？第一次相遇（超一圈）时开始计数，第二次相遇时停止计数。

3.如何判断环的入口点：碰撞点p到连接点的距离=头指针到连接点的距离，因此，分别从碰撞点、头指针开始走，相遇的那个点就是连接点。

为什么呢？需要一个简单的计算过程：
（1）当fast与slow相遇时，show肯定没有走完 链表 ，而fast已经在还里走了n（n>= 1）圈。假设slow走了s步，那么fast走了2s步。fast的步数还等于s走的加上环里转的n圈，所以有：
2s = s + nr。因此，s = nr。
（2）设整个链表长为L，入口据相遇点 X ，起点到入口的距离为a。因为slow指针并没有走完一圈，所以：
a + x = s，带入第一步的结果，有：a + x = nr = (n-1)r + r = (n-1)r + L - a；即：
a = (n-1)r + L -a -x;
这说明：从头结点到入口的距离，等于转了(n-1)圈以后，相遇点到入口的距离。因此，我们可以在链表头、相遇点各设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。

也许大家有一个问题，就是为什么“当fast与slow相遇时，show肯定没有走完链表”。这个问题比较坑，我也没有找到很好的证明。不过大家自己画几个试试，会发现的确是这样。

4.如何判断两个链表（不带环）是否相交？将其中的一个链表首尾相连，然后判断另一个链表是否带环即可。这个比较简单， 程序 就省略了。

[cpp]  view plain copy

1. #include <stdio.h>  

2. typedef struct Node  

3. {  

4.     int val;  

5.     Node *next;  

6. }Node,*pNode;  

7. //判断是否有环  

8. bool isLoop(pNode pHead)  

9. {  

10.     pNode fast = pHead;  

11.     pNode slow = pHead;  

12.     //如果无环，则fast先走到终点  

13.     //当链表长度为奇数时，fast->Next为空  

14.     //当链表长度为偶数时，fast为空  

15.     while( fast != NULL && fast->next != NULL)  

16.     {  

17.         fast = fast->next->next;  

18.         slow = slow->next;  

19.         //如果有环，则fast会超过slow一圈  

20.         if(fast == slow)  

21.         {  

22.             break;  

23.         }  

24.     }  

25.     if(fast == NULL || fast->next == NULL  )  

26.         return false;  

27.     else  

28.         return true;  

29. }  

30. //计算环的长度  

31. int loopLength(pNode pHead)  

32. {  

33.     if(isLoop(pHead) == false)  

34.         return 0;  

35.     pNode fast = pHead;  

36.     pNode slow = pHead;  

37.     int length = 0;  

38.     bool begin = false;  

39.     bool agian = false;  

40.     while( fast != NULL && fast->next != NULL)  

41.     {  

42.         fast = fast->next->next;  

43.         slow = slow->next;  

44.         //超两圈后停止计数，挑出循环  

45.         if(fast == slow && agian == true)  

46.             break;  

47.         //超一圈后开始计数  

48.         if(fast == slow && agian == false)  

49.         {             

50.             begin = true;  

51.             agian = true;  

52.         }  

53.         //计数  

54.         if(begin == true)  

55.             ++length;  

56.     }  

57.     return length;  

58. }  

59. //求出环的入口点  

60. Node* findLoopEntrance(pNode pHead)  

61. {  

62.     pNode fast = pHead;  

63.     pNode slow = pHead;  

64.     while( fast != NULL && fast->next != NULL)  

65.     {  

66.         fast = fast->next->next;  

67.         slow = slow->next;  

68.         //如果有环，则fast会超过slow一圈  

69.         if(fast == slow)  

70.         {  

71.             break;  

72.         }  

73.     }  

74.     if(fast == NULL || fast->next == NULL)  

75.         return NULL;  

76.     slow = pHead;  

77.     while(slow != fast)  

78.     {  

79.         slow = slow->next;  

80.         fast = fast->next;  

81.     }  

82.     return slow;  

83. }