JavaScript判斷單鏈表中是否存在環

binta 發布于2019-08-26 13:33 / 2461人閱讀

摘要：如下圖單鏈表中存在環怎么判斷單鏈表中存在環呢先創造一下帶環的單鏈表代碼如下創建帶環單鏈表結果可見判斷單鏈表是否帶環以下有三種方法第一種方法創建哈希表不過會占用較大的空間不是最佳方法時間復雜度遍歷鏈表將鏈表各節點添加至哈希表中添加前判斷此節點

如下圖, 單鏈表中存在環:

怎么判斷單鏈表中存在環呢?先創造一下帶環的單鏈表:

代碼如下:

創建帶環單鏈表:

結果可見:

判斷單鏈表是否帶環,以下有三種方法:
第一種方法, 創建哈希表,不過會占用較大的空間,不是最佳方法.( 時間復雜度O(n) )

遍歷鏈表,將鏈表各節點添加至哈希表中,添加前判斷此節點是否已存在哈希表中,存在的話說明鏈表中存在環.

結果如下:

檢測到節點B是重復項,說明存在環

第二種方法: 給節點添加visited訪問標記 (時間復雜度O(n)), 不需要額外的空間

遍歷鏈表,每訪問一個新節點,使其visited為1,每次訪問節點前先判斷其visited是否為1,為1則是已訪問過的節點,說明鏈表中存在環.

結果可見:

遍歷鏈表前,鏈表每個節點visited都為0,都沒被訪問過

B節點的visited為1,說明已訪問過B,鏈表中存在環

遍歷后,鏈表中每個節點visited都為1,每個節點都被訪問過

第三種方法: 快慢指針法,設定快指針fast,慢指針slow,每次循環快指針fast移動兩個位置,慢指針移動一個位置
(時間復雜度 O(n)) 需要額外的空間

結果可見:

快指針fast和慢指針slow在節點D相遇,說明鏈表中存在環

原理如下圖:

GPU云服務器云服務器判斷session是否存在 python判斷文件是否存在 mysql 判斷數據庫是否存在是否存在

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/109038.html

LeetCode 之 JavaScript 解答第142題 —— 環形鏈表 II（Linked Li

摘要：說明不允許修改給定的鏈表。算法思路題目要求返回單鏈表中存在循環鏈表的位置。首先，先判斷該單鏈表是否存在循環鏈表用兩個快慢指針分別指向鏈表的頭部，每次移動兩步，每次移動一步，移動的步數是的兩倍。 Time：2019/4/8Title: Linked List Cycle IIDifficulty: mediumAuthor:小鹿題目：Linked List Cycle II Giv...

whidy 2019-08-23 16:51 評論0 收藏0
JAVASCRIPT算法（6）

摘要：還是鏈表算法題目描述給出兩個無環單鏈表判斷和是否相交。所以可以得出另外一種解法，先遍歷鏈表，記住尾節點，然后遍歷鏈表，比較兩個鏈表的尾節點，如果相同則相交，不同則不相交。想法還是奇妙的。算法寫起來不難，難的是想到這個。還是鏈表算法題目描述：給出兩個無環單鏈表A: a1 → a2 ↘ c1 → c2 → c3 → ...

FreeZinG 2019-08-21 17:56 評論0 收藏0
寫一段代碼判斷單向鏈表中有沒有形成環，如果形成環，請找出環的入口處，即P點

摘要：由于要比移動的快，如果有環，一定會先進入環，而后進入環。現在問題就簡單了，由于移動的距離永遠是的一般，因此當遍歷玩整個環長度個節點的時候正好遍歷了個節點，也就是說，此時正好指向距離最遠的點。首先，關于單鏈表中的環，一般涉及到以下問題： 1.給一個單鏈表，判斷其中是否有環的存在； 2.如果存在環，找出環的入口點； 3.如果存在環，求出環上節點的個數； 4.如果存在環，求出鏈表的長度； ...

OldPanda 2019-07-01 13:56 評論0 收藏0
我的面試準備過程--鏈表(更新中)

摘要：拿了小米和美團的，要被延期，失效，工作重新找。把準備過程紀錄下來，共勉。注意，有環的鏈表，此種方法失效。已知兩個單鏈表和各自有序，把它們合并成一個鏈表依然有序寫在最前面導師貪腐出逃美國，兩年未歸，可憐了我。拿了小米和美團的offer，要被延期，offer失效，工作重新找。把準備過程紀錄下來，共勉。鏈表是最常考察的數據結構 // 鏈表定義 public class Node{ ...

30e8336b8229 2019-08-16 10:36 評論0 收藏0