C++語言判斷單鏈表是否有環鏈表 程序源碼

1.問題：如果給定一個單鏈表，如何判斷其是否為有環鏈表
2.方法：
（1）從給定鏈表的第一個節點開始遍歷，每遍歷至一個節點，都將其和所有的前驅節點進行比對，如果為同一個節點，則表明當前鏈表中有環；反之，如果遍歷至鏈表最后一個節點，仍未找到相同的節點，則證明該鏈表中無環。


如上所示，當函數的返回值為 True，表示該鏈表有環；反之若函數返回值為 False，表明鏈表中無環。顯然，此實現方案的時間復雜度為O(n2)。
（2）在一個鏈表中，如果 2 個指針（假設為 H1 和 H2）都從表頭開始遍歷鏈表，其中 H1 每次移動 2 個節點的長度（H1 = H1->next->next）,而 H2 每次移動 1 個節點的長度（H2 = H2->next），如果該鏈表為有環鏈表，則 H1、H2 最終必定會相等；反之，如果該鏈表中無環，則 H1、H2 永遠不會相遇。


本算法的時間復雜度為 O(n)。
源碼：

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. 
   
4. //自定義 bool 類型
   
5. typedef enum Bool
   
6. {
   
7.     False=0,
   
8.     True=1
   
9. }Bool;
   
10. 
    
11. typedef struct link{
    
12.     int data;
    
13.     struct link* next;
    
14. }link;
    
15. 
    
16. link *linkIint(int n)
    
17. {
    
18.     link *head=(link*)malloc(sizeof(link));
    
19.     head->data=1;
    
20.     head->next=NULL;
    
21.     link *phead=head;
    
22.     int i;
    
23.     for(i=2;i<=n;i++)
    
24.     {
    
25.         link *temp=(link*)malloc(sizeof(link));
    
26.         temp->data=i;
    
27.         temp->next=NULL;
    
28. 
    
29.         head->next=temp;
    
30.         head=head->next;
    
31.     }

復制代碼

【必讀】版權免責聲明

1、本主題所有言論和內容純屬會員個人意見，與本論壇立場無關。2、本站對所發內容真實性、客觀性、可用性不做任何保證也不負任何責任，網友之間僅出于學習目的進行交流。3、對提供的數字內容不擁有任何權利，其版權歸原著者擁有。請勿將該數字內容進行商業交易、轉載等行為，該內容只為學習所提供，使用后發生的一切問題與本站無關。 4、本網站不保證本站提供的下載資源的準確性、安全性和完整性;同時本網站也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的損失或傷害。 5、本網站所有軟件和資料均為網友推薦收集整理而來，僅供學習用途使用，請務必下載后兩小時內刪除，禁止商用。6、如有侵犯你版權的，請及時聯系我們（電子郵箱1370723259@qq.com）指出，本站將立即改正。