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

問題描述：

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

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

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

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

分析

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

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

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

錯(cuò)誤

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

哈希

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

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

升級

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

快慢指針

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

時(shí)間復(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;} 

時(shí)間復(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;}

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

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

Tag

LinkedList

Hash

Two Pointers