环形链表 II

　　标题描述：给定一个链表，返回链表开始进入环的第一个节点。如果链表没有循环，则返回null。 　　

　　为了表示给定链表中的环，我们使用整数pos来表示链表的末尾连接到链表的位置(索引从0开始)。如果pos为-1，则该链表中没有环。注意，pos只用来标识环，不会作为参数传入函数。 　　

　　注意：不允许修改给定的链表。 　　

　　进阶： 　　

　　可以用O(1)空间解决这个问题吗？ 　　

　　例子见LeetCode官网。 　　

　　资料来源：LeetCode 　　

　　链接：https://leetcode-cn.com/problems/linked-list-cycle-ii/ 　　

　　版权归领网所有。商业转载请联系官方授权，非商业转载请注明出处。 　　

解法一：哈希表

　　 HashSet确定节点是否重复。 　　

解法二：双指针法

　　使用快慢节点。如果有一个环，这两个节点就会相遇。 　　

　　导入Java . util . hashset；导入Java . util . set；class leet code _ 142 {/* * * hash * * @ param head * @ return */public static listnode检测循环(listnode head){ if(head==null){ return null；} SetListNode nodes=new HashSet()；nodes . add(head)；while (head.next！=null) {//如果哈希表中已经出现了下一个节点，说明循环形成了，下一个节点肯定是循环入点，直接返回If(nodes . contains(head . next)){ return head . next；} nodes . add(head . next)；head=head.next}返回null}/* * *双指针方法* * @ param head * @ return */public static listnode检测周期2(listnode head){ if(head==null){ return null；} ListNode慢=头，快=头；而(快！=null){ slow=slow . next；如果(快.下一个！=null){ fast=fast . next . next；} else {返回null} if(fast==slow){ ListNode ptr=head；while (ptr！=slow){ ptr=ptr . next；slow=slow.next}返回ptr} }返回null} public static void main(String[]args){ ListNode head=new ListNode(3)；head . next=new ListNode(2)；head . next . next=new ListNode(0)；head . next . next . next=new ListNode(-4)；head . next . next . next . next=head . next；system . out . println(detect cycle(head)==null？-1 :检测周期(磁头)。val)；system . out . println(detect cycle 2(head)==null？-1 :检测周期2(头)。val)；}}【每日寄语】世界上有太多不可预知的事情，但不管怎样，社会还是会运行的。一个人的成就再大，在世间万物中也是很渺小的，所以要珍惜每一分钟。