JAVA练习294- 环形链表II

题目概览给定一个链表的头节点head返回链表开始入环的第一个节点。如果链表无环则返回null。如果链表中有某个节点可以通过连续跟踪next指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数pos来表示链表尾连接到链表中的位置索引从 0 开始。如果pos是-1则在该链表中没有环。注意pos不作为参数进行传递仅仅是为了标识链表的实际情况。不允许修改链表。示例 1输入head [3,2,0,-4], pos 1输出返回索引为 1 的链表节点解释链表中有一个环其尾部连接到第二个节点。示例 2输入head [1,2], pos 0输出返回索引为 0 的链表节点解释链表中有一个环其尾部连接到第一个节点。示例 3输入head [1], pos -1输出返回 null解释链表中没有环。提示链表中节点的数目范围在范围[0, 104]内-105 Node.val 105pos的值为-1或者链表中的一个有效索引进阶你是否可以使用O(1)空间解决此题来源142. 环形链表 II - 力扣LeetCode解题分析方法一哈希集合用哈希集合存储遍历过的节点每次遍历判断即可。时间复杂度O(n)空间复杂度O(n)/** * 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) { SetListNode set new HashSet(); ListNode temp head; while(temp ! null) { if (set.contains(temp)) { return temp; } set.add(temp); temp temp.next; } return null; } }方法二快慢指针定义快慢指针一个遍历一个节点一个遍历两个节点如果存在环则两个指针一定会相遇。令头节点到环点的距离为 a从环点到相遇点的距离为 b环长为 c快指针转了 n 圈才相遇。因此可以得到快指针移动的距离为 a nc b。由于快指针的速度是慢指针的两倍因此移动距离也是两倍慢指针的距离为 a b则可以得到 a nc b 2 * ( a b ) 等价于 a b nc。慢指针当前位置是在 b再往前走 a 的距离就刚好一圈走到的位置刚好就是环点。因此我们再相遇时再定义一个指针从表头出发当该指针和慢指针相遇时慢指针刚好走完一圈指针刚好停留在环点。时间复杂度O(n)空间复杂度O(1)/** * 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 a head, b head; int times; while(true) { if (a null || b null || b.next null) { return null; } a a.next; b b.next.next; if (a b) { break; } } ListNode c head; while(c ! a) { a a.next; c c.next; } return c; } }