Linked List Cycle 環(huán)形鏈表

問題描述：

給你一個鏈表的頭節(jié)點 head ，判斷鏈表中是否有環(huán)。

如果鏈表中有某個節(jié)點，可以通過連續(xù)跟蹤 next 指針再次到達(dá)，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)，評測系統(tǒng)內(nèi)部使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。注意：pos 不作為參數(shù)進(jìn)行傳遞 。僅僅是為了標(biāo)識鏈表的實際情況。

如果鏈表中存在環(huán) ，則返回 true 。 否則，返回 false 。

$$\begin{gathered} 鏈表中節(jié)點的數(shù)目范圍是[0,10^4] \\ ?10^5<=Node.val<=10^5 \\ pos為?1或者鏈表中的一個有效索引 \end{gathered}$$

分析

目標(biāo)就是判斷鏈表中是否有環(huán)。

對于無環(huán)鏈表，依次遍歷節(jié)點，最后一定是null，否則就會進(jìn)入循環(huán)，之前已經(jīng)訪問過的節(jié)點，勢必會重新訪問。

所以如何知道節(jié)點是否被訪問過，就是需要解決的問題。

錯誤

有的思路是利用節(jié)點的值，進(jìn)行判斷，很明顯這個思路有缺陷，如果整個鏈表都是相同的值，就明顯無法進(jìn)行判斷。

哈希

而使用哈希表，就可以解決這個問題，它可以保證哈希表中的元素一定是唯一的，不會重復(fù)。
這個原理可以自行Bing，GPT什么的。

所以遍歷的過程中，每遇到一個新節(jié)點，就利用哈希表進(jìn)行判斷是否出現(xiàn)過，如果出現(xiàn)過，說明了節(jié)點一定重復(fù)訪問了，從而說明 有環(huán)。
時間復(fù)雜度 $O(N)$ ,空間復(fù)雜度 $O(N)$
這個是比較常規(guī)的操作，也是大部分的思路。

升級

這個思路很典型，但是隨著數(shù)據(jù)規(guī)模的增加，時空的消耗也會增加。

快慢指針

另一種是雙指針，一個fast，一個slow，fast一次走2步，slow一次一步。
就像圍著操場[環(huán)]跑步，fast一定會追上slow.
其實這里的雙指針也叫快慢指針，該思路還可以解決鏈表的其他問題。

時間復(fù)雜度$O(N)$

空間復(fù)雜度$O(1)$

代碼

哈希

public boolean hasCycle(ListNode head) {Set<ListNode> seen = new HashSet<ListNode>();while (head != null) {if (!seen.add(head)) {return true;}head = head.next;}return false;} 

時間復(fù)雜度$O(N)$

空間復(fù)雜度$O(N)$

快慢指針

public boolean hasCycle(ListNode head) {if(head==null||head.next==null) return false;ListNode vh = new ListNode(-1);vh.next = head;ListNode fast = head.next,slow = vh;while(fast!=null&&fast.next!=null){if(fast==slow) return true;fast = fast.next.next;slow = slow.next;}return false;}

時間復(fù)雜度$O(N)$

空間復(fù)雜度$O(1)$

Tag

LinkedList

Hash

Two Pointers