引言

判斷單鏈表是否成環是一個計算機領域的經典算法問題

如何通過程序判斷傳入的鏈表是否存在環，并且求出環長度、成環點等問題

下面就是一個存在環的單鏈表

基本算法?--?hash

最簡單的方法是創建一個哈希表，將每個節點的地址都存儲起來，如果某個節點的地址出現在了哈希表中，那么首次出現的那個節點就是我們要找的成環的起點了

1）代碼示例

class ListNode:def __init__(self, x):self.val = xself.next = Nonedef get_start_cycle(pHead):nodedict = {}while pHead is not None:if nodedict.get(pHead) is not None:return pHeadnodedict[pHead] = 1pHead = pHead.nextreturn None

2）時間空間復雜度

顯然，在最壞情況下，需要遍歷整個鏈表，所以時間復雜度為?O(N)，空間復雜度為?O(N)

改進算法?--?龜兔賽跑

有過一定生活經驗的人馬上就會想到，在操場的圓形賽道上跑步與在街道上跑馬拉松有什么不同，那就是在操場的賽道上，跑得快的人會從后面追上跑得慢的人

那么，對于單鏈表來說，我們就可以用兩個指針，一個快指針，一個慢指針，從起點出發，快指針如果在出發后追上了慢指針，那就說明單鏈表是存在環的

1）步長選取

那么快指針要選取多大的步長呢？答案是?2，如果選取大于?2?的步長，就會出現快指針直接越過慢指針的情況

代碼示例

typedef struct LinkedNode {int val;LinkedNode *next; } LinkedNode;int is_cycle(LinkedNode *head) {if (head == NULL || head->next == NULL) {return 0;}LinkedNode *slow = head->next, *quick = head->next->next;while (quick != NULL && quick->next != NULL) {if (quick == slow) {return 1;}quick = quick->next->next;slow = slow->next;}return 0; }

時間空間復雜度

因為快指針繞一圈，慢指針只能繞半圈，所以我們可以得出兩指針相遇時，慢指針一定沒有繞滿一圈

而不成環的情況下，快指針一定先到達終點，所以時間復雜度為?O(n)

整個過程沒有額外分配空間，所以空間復雜度是?O(1)

如何通過龜兔賽跑法求出成環點

原理推導

假設環長為?d，初始距入口點為?n，入口點距相遇點為?m

假設此時快指針已經繞了?k?圈，那么我們可以得到公式：

m+n?=?k*d

但是，我們要求的是入口點距起始點的距離?m，所以我們需要進行移項：

m?=?k*d-n

因為兩指針相遇時，快指針一定至少已經繞滿一圈，所以?k?一定大于等于?1，而?d?-?n?就是從相遇點繼續前進到起始點的距離，所以我們可以進一步分解?k*d：

m?=?(k-1)*d?+?(d-n)

因此，我們可以發現，從起始點出發到成環點的距離與相遇點出發到成環點的距離之間只差?(k-1)?個

也就是說，兩個指針如果以相同步長分別從起始點與相遇點出發，相遇時一定在成環點

代碼示例

LinkedNode *get_cycle_start_node(LinkedNode *head) {if (head == NULL || head->next == NULL) {return NULL;}LinkedNode *slow = head->next, *quick = head->next->next;while (quick != NULL && quick->next != NULL) {if (quick == slow) {quick = head;while (slow != quick) {slow = slow->next;quick = quick->next;}return slow;}quick = quick->next->next;slow = slow->next;}return NULL; }

時間空間復雜度

?

我們看到，無論自相遇點出發的指針繞環多少圈，自起始點出發的指針最多遍歷?n-1?個元素，所以其時間復雜度也是?O(n)?的，而空間復雜度為?O(1)

?

找出成環點的另一個思路?--?斷鏈法

三十六計里有一計?--?過河拆橋

在已知單鏈表成環的前提下，我們每走一步都把前面的路拆掉，那么當我們發現無路可走時，那就說明我們又回到了原來的路上，那個點自然就是成環點了

?

代碼示例

#include <stdio.h> #include <malloc.h>#define null NULLtypedef struct LinkedNode {int val;LinkedNode *next; } LinkedNode;int is_cycle(LinkedNode *head) {if (head == null || head->next == null) {return 0;}LinkedNode *slow = head->next, *quick = head->next->next;while (quick != null && quick->next != null) {if (quick == slow) {return 1;}quick = quick->next->next;slow = slow->next;}return 0; }LinkedNode *get_cycle_start_node(LinkedNode *head) {if (!is_cycle(head)) {return null;}while (head->next != null) {LinkedNode *temp = head->next;head->next = null;head = temp;}return head; }

?

?

?

時間空間復雜度

?

這個算法先判斷是否成環，后從頭到尾最多遍歷?n-1?個元素，所以時間復雜度也是?O(n)，而空間復雜度為?O(1)

總結

以上是生活随笔為你收集整理的经典算法题 -- 判断单链表是否成环及寻找成环节点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。