leetcode 142. Linked List Cycle II 龟兔赛跑（循环指针）

上一题 leetcode 141. Linked List Cycle 相同解法 leetcode 287. Find the Duplicate Number

题意

如果有环，找出环第一个出现的节点，如果没有，返回null。

解1

时间O(1)，空间O(N)

// Runtime: 3 ms, faster than 23.27% of Java online submissions for Linked List Cycle II. //Memory Usage: 39.7 MB, less than 5.94% of Java online submissions for Linked List Cycle II. public ListNode detectCycle(ListNode head) { Set<ListNode> visited = new HashSet<>(); while (head != null) { if (!visited.add(head)) return head; head = head.next; } return null; }

解2

时间O(1)，空间O(1) 龟兔赛跑，兔子每次2步，乌龟1步。 不能相遇返回null。 相遇时乌龟跑了一段路径，兔子也跑了这些，还额外饶了n圈，因为兔子跑了2倍乌龟距离，所以乌龟跑的距离等于n圈。此时（相遇），新的乌龟从头开始和乌龟以相同的速度跑，一定在begin处相遇。

// Runtime: 0 ms, faster than 100.00% of Java online submissions for Linked List Cycle II. //Memory Usage: 38.8 MB, less than 5.94% of Java online submissions for Linked List Cycle II. public ListNode detectCycle(ListNode head) { ListNode fast = head; ListNode slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (fast == slow) { ListNode rst = head; while (slow != rst) { slow = slow.next; rst = rst.next; } return rst; } } return null; }