程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 如何判斷單鏈表中是否存在環

如何判斷單鏈表中是否存在環

編輯:關於C語言

  有一個單鏈表,其中可能有一個環,也就是某個節點的next指向的是鏈表中在它之前的節點,這樣在鏈表的尾部形成一環。
  現在需要解決的問題有以下兩個:如何判斷一個鏈表是不是這類鏈表?
  如果鏈表為存在環,如何找到環的入口點?
  判斷鏈表是否存在環,辦法為:設置兩個指針(fast, slow),初始值都指向頭,slow每次前進一步,fast每次前進二步,如果鏈表存在環,則fast必定先進入環,而slow後進入環,兩個指針必定相遇。(當然,fast先行頭到尾部為NULL,則為無環鏈表)程序如下:
  01 bool I***itsLoop(slist *head)
  02 { 03     slist *slow = head, *fast = head;04 05     while ( fast && fast->next )
  06     { 07         slow = slow->next;08         fast = fast->next->next;09         if ( slow == fast ) break;10     } 11 12     return !(fast == NULL || fast->next == NULL);13 }關於找到找到環的入口點的問題,當fast若與slow相遇時,slow肯定沒有走遍歷完鏈表,而fast已經在環內循環了n圈(1<=n)。假設slow走了s步,則fast走了2s步(fast步數還等於s 加上在環上多轉的n圈),設環長為r,則:
  1 2s = s + nr 2 s= nr設整個鏈表長L,入口環與相遇點距離為x,起點到環入口點的距離為a.
  1 a + x = nr 2 a + x = (n – 1)r +r = (n-1)r + L - a 3 a = (n-1)r + (L – a – x)
  (L – a – x)為相遇點到環入口點的距離,由此可知,從鏈表頭到環入口點等於(n-1)循環內環+相遇點到環入口點,於是我們從鏈表頭、與相遇點分別設一個指針,每次各走一步,兩個指針必定相遇,且相遇第一點為環入口點。程序描述如下:
  01 slist* FindLoopPort(slist *head)
  02 { 03     slist *slow = head, *fast = head;04 05     while ( fast && fast->next )
  06     { 07         slow = slow->next;08         fast = fast->next->next;09         if ( slow == fast ) break;10     } 11 12     if (fast == NULL || fast->next == NULL)
  13         return NULL;14 15     slow = head;16     while (slow != fast)
  17     { 18          slow = slow->next;19          fast = fast->next;20     } 21 22     return slow;23 }判斷兩個單鏈表是否相交,如果相交,給出相交的第一個點(兩個鏈表都不存在環)。比較好的方法有兩個:將其中一個鏈表首尾相連,檢測另外一個鏈表是否存在環,如果存在,則兩個鏈表相交,而檢測出來的依賴環入口即為相交的第一個點。
  如果兩個鏈表相交,那個兩個鏈表從相交點到鏈表結束都是相同的節點,我們可以先遍歷一個鏈表,直到尾部,再遍歷另外一個鏈表,如果也可以走到同樣的結尾點,則兩個鏈表相交。
  這時我們記下兩個鏈表length,再遍歷一次,長鏈表節點先出發前進(lengthMax-lengthMin)步,之後兩個鏈表同時前進,每次一步,相遇的第一點即為兩個鏈表相交的第一個點。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved