- 相關(guān)推薦
C語(yǔ)言單向鏈表環(huán)測(cè)試并返回環(huán)起始節(jié)點(diǎn)的方法
有時(shí)候我們需要測(cè)試一個(gè)單向鏈表是否存在環(huán)。最土鱉的方法就是改變鏈表的數(shù)據(jù)結(jié)構(gòu)，給每個(gè)節(jié)點(diǎn)添加一個(gè)bool變量，在未測(cè)試時(shí)全部初始化為false，然后遍歷鏈表，每訪問(wèn)一個(gè)節(jié)點(diǎn)，先測(cè)試其bool成員來(lái)確定這個(gè)節(jié)點(diǎn)是否被訪問(wèn)過(guò)，如果為true，則表示訪問(wèn)過(guò)，則有環(huán)，否則設(shè)置bool成員為true，表明訪問(wèn)過(guò)，然后繼續(xù)測(cè)試。下面，小編為大家搜索整理了C語(yǔ)言單向鏈表環(huán)測(cè)試并返回環(huán)起始節(jié)點(diǎn)的方法，希望能給大家?guī)?lái)幫助!更多精彩內(nèi)容請(qǐng)及時(shí)關(guān)注我們應(yīng)屆畢業(yè)生考試網(wǎng)!
如果不改變數(shù)據(jù)結(jié)構(gòu)的話，我們有以下的解決方案：
1. 測(cè)試是否有環(huán)：
我們可以構(gòu)建兩個(gè)迭代器來(lái)遍歷鏈表，一個(gè)每一次移動(dòng)一個(gè)節(jié)點(diǎn)，另外一個(gè)每次移動(dòng)兩個(gè)節(jié)點(diǎn)。如果這兩個(gè)一快一慢的土鱉迭代器相遇了，也就是說(shuō)他們?cè)谀硞�(gè)時(shí)刻都到了同一個(gè)節(jié)點(diǎn)，那么我們可以肯定有環(huán)存在。直觀的理解就是讓兩個(gè)土鱉一快一慢在400米環(huán)形跑道上各選一個(gè)位置，然后同時(shí)順時(shí)針做死了跑，那么這兩個(gè)土鱉總能相遇,因?yàn)橐粋�(gè)比另外一個(gè)快。
如果需要嚴(yán)謹(jǐn)?shù)淖C明，我們可以這樣理解。假設(shè)在某個(gè)迭代時(shí)刻，兩個(gè)土鱉迭代器(以后簡(jiǎn)稱(chēng)土鱉)都進(jìn)入了環(huán)，一個(gè)距環(huán)起始點(diǎn)為i，一個(gè)距環(huán)起始點(diǎn)為j。這個(gè)假設(shè)必然有成立的時(shí)候，因?yàn)榕苤苤麄兛倳?huì)進(jìn)入環(huán)，而且一旦進(jìn)入那就出不來(lái)了，只能做死了跑。然后假設(shè)又跑了一會(huì)兒，這兩個(gè)土鱉相遇了，一個(gè)土鱉跑了x步，一個(gè)跑了2x步。如果這個(gè)環(huán)總共長(zhǎng)n,也就是說(shuō)慢土鱉需要跑n步才能跑完一圈。然后我們可以得出i+x和j+2x對(duì)于n同余，也就是說(shuō)i+x和j+2x除以n的余數(shù)是相同的，寫(xiě)成同余等式就是(i+x)=j+2x(mod n) ，根據(jù)同余加減法性質(zhì)，我們可以讓上面的式子減去x=x(mod m)，得到i=(j+x)(mod m)。因?yàn)閤未知，所以上面的式子是個(gè)同余方程，i、j都是普通整數(shù)，很明顯這個(gè)方程是有解的。例如2=(1+x)(mod 5)的一個(gè)簡(jiǎn)單解就是1。所以這兩個(gè)土鱉跑著跑著總會(huì)相遇。也就是說(shuō)我們上面檢測(cè)環(huán)的算法可行，不會(huì)死循環(huán)。
2. 獲取環(huán)起始點(diǎn)：
基于問(wèn)題1的分析，快土鱉和慢土鱉總會(huì)在某個(gè)節(jié)點(diǎn)相遇，假設(shè)這個(gè)點(diǎn)為cross。同事假設(shè)環(huán)起始點(diǎn)為start。一個(gè)顯然的事實(shí)是，當(dāng)兩個(gè)土鱉相遇時(shí)，慢土鱉跑過(guò)的路徑是快土鱉的一半。這樣的話，在相遇前，當(dāng)慢土鱉跑了一般的時(shí)候，快土鱉已經(jīng)經(jīng)過(guò)了相遇點(diǎn)(落腳或者跨越)。這樣的話當(dāng)慢土鱉跑完后半段的時(shí)候，快土鱉從相遇點(diǎn)開(kāi)始又跑了同樣的路程到達(dá)了相遇點(diǎn)，這個(gè)路程的長(zhǎng)度等于慢土鱉總共跑的長(zhǎng)度。現(xiàn)在牛逼的地方來(lái)了，如果慢土鱉從頭開(kāi)始跑的時(shí)候，有另外一個(gè)慢土鱉從相遇點(diǎn)cross開(kāi)始跑，那么他們兩個(gè)也會(huì)在相遇點(diǎn)相遇，我們稱(chēng)這兩個(gè)土鱉分別為A和B。土鱉B走的路程和快土鱉后半段時(shí)間走過(guò)的路程是完全一樣的，唯一的區(qū)別就是他慢一點(diǎn)而已。現(xiàn)在第二個(gè)牛逼的地方來(lái)了，因?yàn)槁流MA和B的速度是一樣的，那么他們?cè)谙嘤鳇c(diǎn)之前的節(jié)奏也是一樣的，也就是說(shuō)他們?cè)谙嘤鳇c(diǎn)值錢(qián)已經(jīng)相遇了，而且一同樣的速度相伴走到了相遇點(diǎn)cross。他們從什么時(shí)候相遇開(kāi)始這段快樂(lè)的旅程呢，當(dāng)然是環(huán)起始點(diǎn)start。我們可以讓慢土鱉A和B從相遇點(diǎn)倒退，這樣就能理解為什么他們?cè)趕tart點(diǎn)相遇了。OK，現(xiàn)在我們有了解決方案，讓慢土鱉A從鏈表頭start開(kāi)始跑，讓另外一個(gè)慢土鱉從相遇點(diǎn)cross開(kāi)始跑，他們第一次的相遇點(diǎn)就是環(huán)起始點(diǎn)。
大功告成，標(biāo)點(diǎn)符號(hào)(廢話)有點(diǎn)多，大家不要介意。
下面是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 }
【C語(yǔ)言單向鏈表環(huán)測(cè)試并返回環(huán)起始節(jié)點(diǎn)的方法】相關(guān)文章：
C語(yǔ)言的循環(huán)鏈表和約瑟夫環(huán)09-29
C語(yǔ)言測(cè)試試題及答案08-02
C語(yǔ)言測(cè)試題及答案07-03
C語(yǔ)言的冒泡排序方法08-22
常用C語(yǔ)言測(cè)試題及答案09-12
C語(yǔ)言考試模擬測(cè)試題10-21
測(cè)試C語(yǔ)言功力的幾個(gè)問(wèn)題09-07
Java程序調(diào)用C/C++語(yǔ)言函數(shù)的方法07-31
C語(yǔ)言返回多個(gè)值的方法07-07