判斷一個單鏈表是否有環及環入口

作者：ACb0y

鏈接：https://segmentfault.com/a/1190000008951676

碼農有道作了部分修改

題目及要求

題目：如何判斷一個單鏈表是否有環？若有環，如何找出環的入口節點。要求如下：

1：不允許修改鏈表結構。

2：時間複雜度O(n)，空間複雜度O(1)。

判斷是否有環

如果鏈表有環，那麼在遍歷鏈表時則會陷入死循環，利用這個特徵，我們可以設計這樣的演算法。

1：使用一個slow指針，一個fast指針。

2：slow指針一次往後遍歷以1個節點，fast指針一次往後遍歷2個節點，一直做這樣的操作。

圖一

圖二

圖三

3：如果走到某一步，當slow指針和falst指針相同了，則說明環有節點。

圖四

環的入口節點

我們假定鏈表頭到環入口的距離是len，環入口到slow和fast交匯點的距離為x，環的長度為R。slow和fast第一次交匯時，設slow走的長度為：d = len + x，而fast走的長度為：2d = len + nR + x，(n >= 1)，從而我們可以得知：2len + 2x = len + nR + x，即len = nR - x，(n >= 1)，於是我們可以得到這樣的演算法。

1：使用一個cur指針指向鏈表頭節點，一個inter指針指向第一次的交匯點。

圖一

2：cur指針和inter指針一起往後遍歷。

圖二

圖三

3：cur指針和inter指針相等時，cur和inter指針指向的就是環的入口節點。

圖四

inter指針在遍歷過程中可能多次(n >= 1)經過環入口節點，但當cur指針第一次達到入口節點時，inter指針此時必然也指向入口節點。

代碼實現

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

* ListNode(int x) : val(x), next(NULL) {}

* };

*/

classSolution {

public:ListNode*detectCycle(ListNode*head) {

if(NULL==head)returnNULL; ListNode*fast=head; ListNode*slow=head;

while(1) { fast=fast->next?fast->next:NULL;

if(NULL==fast)break;

fast=fast->next?fast->next:NULL;if(NULL==fast)break; slow=slow->next;if(slow==fast)break; }if(NULL==fast)returnNULL; ListNode*cur=head; ListNode*inter=slow;while(cur!=inter) { cur=cur->next; inter=inter->next; }returncur; }

};

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！