142. 环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
思路，参考storm大神。
如果链表中存在环，则链表的尾结点的 next 指针指向链表中的一个结点，被指向的结点为链表开始入环的结点。从链表的头结点 head 开始遍历链表，如果链表存在环，则在访问尾结点之后会重复访问链表开始入环的结点，链表开始入环的结点是第一个被重复访问的结点。 如果链表中没有环，则任何结点都不会被重复访问。 因此可以遍历链表，寻找第一个被重复访问的结点。为了判断是否有结点被重复访问，可以使用哈希集合存储访问过的结点。 在遍历链表的过程中将访问到的每个结点加入哈希集合，遇到的第一个已经在哈希集合中的结点即为链表开始入环的结点，返回该结点。如果遍历链表结束到达 null 时仍没有遇到已经在哈希集合中的结点，则链表中没有环，返回 null。
/**

• Definition for singly-linked list.
• class ListNode {

• int val;
  

• ListNode next;
  

• ListNode(int x) {
  

•     val = x;
  

•     next = null;
  

• }
  

• }
  */
  public class Solution {
  public ListNode detectCycle(ListNode head) {
  ListNode node;
  node=head;
  Set hs = new HashSet();
  while(node!=null)
  {
  if(!hs.contains(node))
  {
  hs.add(node);
  }else
  {
  return node;
  }
  node=node.next;
  }
  return node;
  }
  }