1.題目
給定一個鏈表的頭節(jié)點 head 亦鳞，返回鏈表開始入環(huán)的第一個節(jié)點喳篇。 如果鏈表無環(huán)藤乙，則返回 null。
如果鏈表中有某個節(jié)點阶界，可以通過連續(xù)跟蹤 next 指針再次到達(dá)虹钮，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)膘融，評測系統(tǒng)內(nèi)部使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）芙粱。如果 pos 是 -1，則在該鏈表中沒有環(huán)氧映。注意：pos 不作為參數(shù)進(jìn)行傳遞春畔，僅僅是為了標(biāo)識鏈表的實際情況。
不允許修改 鏈表岛都。
image.png
image.png
2.方法
- 哈希表
判斷循環(huán)鏈表的方法就是判斷當(dāng)最后一個節(jié)點是否在最后指向它的后繼結(jié)點是否在拐迁，哈希表中存在，如果存在疗绣，則確定是循環(huán)鏈表线召，否則不是。 - 總結(jié)：循環(huán)在哈希表中添加節(jié)點多矮，如果節(jié)點有之前添加過之后缓淹，判斷就不能進(jìn)行添加節(jié)點，從而返回這個節(jié)點塔逃。
3.代碼
/**
* Definition for singly-linked list.
* class ListNode(var _x: Int = 0) {
* var next: ListNode = null
* var x: Int = _x
* }
*/
def detectCycle(head: ListNode): ListNode = {
var pos = head
import scala.collection.mutable.HashSet
val hashSet = new HashSet[ListNode]()
while(pos!=null){
if(!hashSet.add(pos)) return pos
pos = pos.next
}
return null
}
