环形链表 II

1.题目

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。

image.png

image.png

2.方法

• 哈希表
  判断循环链表的方法就是判断当最后一个节点是否在最后指向它的后继结点是否在，哈希表中存在，如果存在，则确定是循环链表，否则不是。
• 总结：循环在哈希表中添加节点，如果节点有之前添加过之后，判断就不能进行添加节点，从而返回这个节点。

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
  }