C語言單向鏈表環(huán)測試并返回環(huán)起始節(jié)點

有時候我們需要測試一個單向鏈表是否存在環(huán)。最土鱉的方法就是改變鏈表的數(shù)據(jù)結(jié)構(gòu)，給每個節(jié)點添加一個bool變量，在未測試時全部初始化為false，然后遍歷鏈表，每訪問一個節(jié)點，先測試其bool成員來確定這個節(jié)點是否被訪問過，如果為true，則表示訪問過，則有環(huán)，否則設(shè)置bool成員為true，表明訪問過，然后繼續(xù)測試。

如果不改變數(shù)據(jù)結(jié)構(gòu)的話，我們有以下的解決方案：

1. 測試是否有環(huán)：

我們可以構(gòu)建兩個迭代器來遍歷鏈表，一個每一次移動一個節(jié)點，另外一個每次移動兩個節(jié)點。如果這兩個一快一慢的土鱉迭代器相遇了，也就是說他們在某個時刻都到了同一個節(jié)點，那么我們可以肯定有環(huán)存在。直觀的理解就是讓兩個土鱉一快一慢在400米環(huán)形跑道上各選一個位置，然后同時順時針做死了跑，那么這兩個土鱉總能相遇,因為一個比另外一個快。

如果需要嚴(yán)謹(jǐn)?shù)淖C明，我們可以這樣理解。假設(shè)在某個迭代時刻，兩個土鱉迭代器(以后簡稱土鱉)都進(jìn)入了環(huán)，一個距環(huán)起始點為i，一個距環(huán)起始點為j。這個假設(shè)必然有成立的時候，因為跑著跑著他們總會進(jìn)入環(huán)，而且一旦進(jìn)入那就出不來了，只能做死了跑。然后假設(shè)又跑了一會兒，這兩個土鱉相遇了，一個土鱉跑了x步，一個跑了2x步。如果這個環(huán)總共長n,也就是說慢土鱉需要跑n步才能跑完一圈。然后我們可以得出i+x和j+2x對于n同余，也就是說i+x和j+2x除以n的余數(shù)是相同的，寫成同余等式就是(i+x)=j+2x(mod n) ，根據(jù)同余加減法性質(zhì)，我們可以讓上面的式子減去x=x(mod m)，得到i=(j+x)(mod m)。因為x未知，所以上面的式子是個同余方程，i、j都是普通整數(shù)，很明顯這個方程是有解的。例如2=(1+x)(mod 5)的一個簡單解就是1。所以這兩個土鱉跑著跑著總會相遇。也就是說我們上面檢測環(huán)的算法可行，不會死循環(huán)。

2. 獲取環(huán)起始點：

基于問題1的分析，快土鱉和慢土鱉總會在某個節(jié)點相遇，假設(shè)這個點為cross。同事假設(shè)環(huán)起始點為start。一個顯然的事實是，當(dāng)兩個土鱉相遇時，慢土鱉跑過的路徑是快土鱉的一半。這樣的話，在相遇前，當(dāng)慢土鱉跑了一般的時候，快土鱉已經(jīng)經(jīng)過了相遇點(落腳或者跨越)。這樣的話當(dāng)慢土鱉跑完后半段的時候，快土鱉從相遇點開始又跑了同樣的路程到達(dá)了相遇點，這個路程的長度等于慢土鱉總共跑的長度。現(xiàn)在牛逼的地方來了，如果慢土鱉從頭開始跑的時候，有另外一個慢土鱉從相遇點cross開始跑，那么他們兩個也會在相遇點相遇，我們稱這兩個土鱉分別為A和B。土鱉B走的路程和快土鱉后半段時間走過的路程是完全一樣的，唯一的區(qū)別就是他慢一點而已。現(xiàn)在第二個牛逼的地方來了，因為慢土鱉A和B的速度是一樣的，那么他們在相遇點之前的節(jié)奏也是一樣的，也就是說他們在相遇點值錢已經(jīng)相遇了，而且一同樣的速度相伴走到了相遇點cross。他們從什么時候相遇開始這段快樂的旅程呢，當(dāng)然是環(huán)起始點start。我們可以讓慢土鱉A和B從相遇點倒退，這樣就能理解為什么他們在start點相遇了。OK，現(xiàn)在我們有了解決方案，讓慢土鱉A從鏈表頭start開始跑，讓另外一個慢土鱉從相遇點cross開始跑，他們第一次的相遇點就是環(huán)起始點。

大功告成，標(biāo)點符號(廢話)有點多，大家不要介意。

下面是C++代碼：

1 #include

2 #include

3

4 template

5 struct Node

6 {

7 T value;

8 Node* next;

9 };

10

11 //Test if a linked list has circle

12 template

13 bool hasLoop(Node* linkedList, Node** loopCross = NULL)

14 {

15 //empty linked list, no circle

16 if(linkedList == NULL || loopCross == NULL) return false;

17

18 Node* slowWalker = linkedList;

19 Node* quickWalker = linkedList;

20 while(quickWalker != NULL && quickWalker->next != NULL)

21 {

22 // move the walker

23 slowWalker = slowWalker->next; //one each step

24 quickWalker = quickWalker->next->next; //two each step

25 if(slowWalker == quickWalker)

26 {

27 //has circle

28 *loopCross = slowWalker;

29 return true;

30 }

31 }

32

33 return false;

34 }

35

36 //Get the loop start node

37 template

38 Node* getLoopStart(Node* linkedList, Node* loopCross)

39 {

40 Node* startFromHead = linkedList;

41 Node* startFromCross = loopCross;

42 // Move one pointer from head and move another from the cross node.

43 // They will meet each other at the loop start node.

44 while(startFromHead != startFromCross)

45 {

46 startFromHead = startFromHead->next;

47 startFromCross = startFromCross->next;

48 }

49 return startFromHead;

50 }

51

52 int main()

53 {

54 Node* linkedList = new Node();

55 linkedList->value = 0;

56 linkedList->next = NULL;

57

58 Node* pNode = linkedList;

59 Node* crossNode = NULL;

60

61 for(int i = 1; i < 100; i++)

62 {

63 Node* tem = new Node();

64 tem->value = i;

65 tem->next = NULL;

66

67 pNode->next = tem;

68 pNode = tem;

69 // set the cross node;

70 if(i == 66)

71 crossNode = tem;

72 }

73

74 printf("test normal linked list:\n");

75 if(hasLoop(linkedList))

76 printf("has circle.\n");

77 else

78 printf("no circle.\n");

79

80 printf("test circle linked list:\n");

81 pNode->next = crossNode; // Create a circle

82

83 Node* loopCross = NULL;

84 if(hasLoop(linkedList, &loopCross))

85 {

86 printf("has circle.\n");

87 Node* loopStart = getLoopStart(linkedList, loopCross);

88 if(loopStart != NULL)

89 printf("the value of the circle start node is %d\n", loopStart->value);

90 }

91 else

92 printf("no circle.");

93 }

深圳北大青鳥http://m.sbsnmc.com