一.面試題目
給定一個鍊表,判斷鍊表中是否有環.
難度升級: 試試能否在不使用額外空間解決此問題?
二.解決方案(哈希表)
思路
我們可以通過檢查一個結點此前是否被訪問過來判斷鍊表是否為環形鍊表.常用方法,一般是使用哈希表.
算法
我們遍歷所有的節點並在哈希表中存儲每個結點的引用(或內存地址).如果當前節點為空結點null,表示我們已經檢測到鍊表的末尾的下一個節點.那麼表示我們已經完成了鍊表的遍歷,並且此鍊表不是環形鍊表.如果當前結點的引用已經存在過哈希表中,那麼即可立馬返回true(表示此鍊表為環形鍊表).
三.代碼
Java Code
四.複雜度分析
- 時間複雜度: O(n),對於含有n個元素的鍊表,我們訪問每個元素最多一次.添加一個結點到哈希表中只需要花費O(1)的時間.
- 空間複雜度:O(n),空間取決於添加哈希表中的元素數目.最多可以添加n個元素.