[Interview] 3. How to Detect a Cycle in a Linked List? How to Calculate the Cycle's Length?

1. How to detect a cycle? If you have two pointers, one moving fast and one moving slow, after a certain number of steps, the fast pointer will eventually overtake the slow pointer by one full cycle.

2. How to calculate the length of the cycle? Start counting when they meet for the first time (after the fast pointer has completed one cycle), and stop counting when they meet for the second time.

3. How to find the entry point of the cycle: The distance from the collision point (p) to the cycle's entry point is equal to the distance from the head pointer to the cycle's entry point. Therefore, if you start one pointer from the collision point and another from the head pointer, and both move one step at a time, the point where they meet will be the cycle's entry point.

Why? Here's a simple derivation: (1) When fast and slow pointers meet, the slow pointer has definitely not traversed the entire linked list, while the fast pointer has completed n (n >= 1) cycles within the loop. Assume the slow pointer has moved s steps, then the fast pointer has moved 2s steps. The fast pointer's steps are also equal to the slow pointer's steps plus n full cycles within the loop, so we have: 2s = s + nr. Therefore, s = nr. (2) Let the total length of the linked list be L, the distance from the entry point to the meeting point be X, and the distance from the start to the entry point be a. Since the slow pointer has not completed a full cycle: a + x = s. Substituting the result from the first step, we get: a + x = nr = (n-1)r + r = (n-1)r + L - a; that is: a = (n-1)r + L - a - x; This shows that the distance from the head node to the entry point is equal to the distance from the meeting point to the entry point after (n-1) cycles. Therefore, we can place one pointer at the head of the list and another at the meeting point. By moving both pointers one step at a time, they are guaranteed to meet, and their first meeting point will be the entry point of the cycle.

Perhaps some of you might have a question: why is it that "when fast and slow pointers meet, the slow pointer has definitely not traversed the entire linked list"? This question is a bit tricky, and I haven't found a perfect proof for it. However, if you try drawing a few examples yourself, you'll find that it is indeed the case.

4. How to determine if two (non-cyclic) linked lists intersect? Connect the tail of one linked list to its head, and then check if the other linked list contains a cycle. This is relatively simple, so the code is omitted.

[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. }