資訊專欄INFORMATION COLUMN
摘要：如下圖單鏈表中存在環(huán)怎么判斷單鏈表中存在環(huán)呢先創(chuàng)造一下帶環(huán)的單鏈表代碼如下創(chuàng)建帶環(huán)單鏈表結(jié)果可見判斷單鏈表是否帶環(huán)以下有三種方法第一種方法創(chuàng)建哈希表不過會占用較大的空間不是最佳方法時間復雜度遍歷鏈表將鏈表各節(jié)點添加至哈希表中添加前判斷此節(jié)點
如下圖, 單鏈表中存在環(huán):
怎么判斷單鏈表中存在環(huán)呢?先創(chuàng)造一下帶環(huán)的單鏈表:
代碼如下:
創(chuàng)建帶環(huán)單鏈表:
結(jié)果可見:
判斷單鏈表是否帶環(huán),以下有三種方法:
第一種方法, 創(chuàng)建哈希表,不過會占用較大的空間,不是最佳方法.( 時間復雜度O(n) )
遍歷鏈表,將鏈表各節(jié)點添加至哈希表中,添加前判斷此節(jié)點是否已存在哈希表中,存在的話說明鏈表中存在環(huán).
結(jié)果如下:
檢測到節(jié)點B是重復項,說明存在環(huán)
第二種方法: 給節(jié)點添加visited訪問標記 (時間復雜度O(n)), 不需要額外的空間
遍歷鏈表,每訪問一個新節(jié)點,使其visited為1,每次訪問節(jié)點前先判斷其visited是否為1,為1則是已訪問過的節(jié)點,說明鏈表中存在環(huán).
結(jié)果可見:
遍歷鏈表前,鏈表每個節(jié)點visited都為0,都沒被訪問過
B節(jié)點的visited為1,說明已訪問過B,鏈表中存在環(huán)
遍歷后,鏈表中每個節(jié)點visited都為1,每個節(jié)點都被訪問過
第三種方法: 快慢指針法,設(shè)定快指針fast,慢指針slow,每次循環(huán)快指針fast移動兩個位置,慢指針移動一個位置
(時間復雜度 O(n)) 需要額外的空間
結(jié)果可見:
快指針fast和慢指針slow在節(jié)點D相遇,說明鏈表中存在環(huán)
原理如下圖:
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/109038.html
摘要：說明不允許修改給定的鏈表。算法思路題目要求返回單鏈表中存在循環(huán)鏈表的位置。首先，先判斷該單鏈表是否存在循環(huán)鏈表用兩個快慢指針分別指向鏈表的頭部，每次移動兩步，每次移動一步，移動的步數(shù)是的兩倍。 Time：2019/4/8Title: Linked List Cycle IIDifficulty: mediumAuthor:小鹿 題目：Linked List Cycle II Giv...
摘要：還是鏈表算法題目描述給出兩個無環(huán)單鏈表判斷和是否相交。所以可以得出另外一種解法，先遍歷鏈表，記住尾節(jié)點，然后遍歷鏈表，比較兩個鏈表的尾節(jié)點，如果相同則相交，不同則不相交。想法還是奇妙的。算法寫起來不難，難的是想到這個。 還是鏈表算法 題目描述：給出兩個無環(huán)單鏈表A: a1 → a2 ↘ c1 → c2 → c3 → ...
摘要：由于要比移動的快，如果有環(huán)，一定會先進入環(huán)，而后進入環(huán)。現(xiàn)在問題就簡單了，由于移動的距離永遠是的一般，因此當遍歷玩整個環(huán)長度個節(jié)點的時候正好遍歷了個節(jié)點，也就是說，此時正好指向距離最遠的點。 首先，關(guān)于單鏈表中的環(huán)，一般涉及到以下問題： 1.給一個單鏈表，判斷其中是否有環(huán)的存在； 2.如果存在環(huán)，找出環(huán)的入口點； 3.如果存在環(huán)，求出環(huán)上節(jié)點的個數(shù)； 4.如果存在環(huán)，求出鏈表的長度； ...
摘要：拿了小米和美團的，要被延期，失效，工作重新找。把準備過程紀錄下來，共勉。注意，有環(huán)的鏈表，此種方法失效。已知兩個單鏈表和各自有序，把它們合并成一個鏈表依然有序 寫在最前面 導師貪腐出逃美國，兩年未歸，可憐了我。拿了小米和美團的offer，要被延期，offer失效，工作重新找。把準備過程紀錄下來，共勉。 鏈表是最?？疾斓臄?shù)據(jù)結(jié)構(gòu) // 鏈表定義 public class Node{ ...
閱讀 2273·2023-04-25 23:15
閱讀 1937·2021-11-22 09:34
閱讀 1561·2021-11-15 11:39
閱讀 968·2021-11-15 11:37
閱讀 2162·2021-10-14 09:43
閱讀 3502·2021-09-27 13:59
閱讀 1511·2019-08-30 15:43
閱讀 3475·2019-08-30 15:43
