关于我的 Leetcode 题目解答，代码前往 Github：https://github.com/chenxiangcyr/leetcode-answers
Floyd算法分为两个不同的阶段。第一个阶段是判断在链表中是否有环路，如果不存在就马上返回空，也就不存在第二阶段。第二个阶段就是找到环路的入口。
第一阶段：
初始化两个指针（快的兔子hare）和（慢的乌龟tortoise）。接下来，兔子hare和乌龟tortoise从同一个节点出发（头节点），乌龟tortoise每次走一个节点，兔子hare每次走两个节点。
如果他们在前进若干步后在同一个节点相遇，我们就返回这个节点，如果最终没有返回节点信息，而是返回空，则代表不存在环路。
第二阶段：
由于第一阶段确定了有环路，第二阶段就是找环的入口节点。接下来初始化两个个指针，ptr1：它指向头节点， ptr2：指向第一阶段找到的相遇节点。
然后将他们以一次移动一个节点的速度向前移动，直到他们再次相遇为止，并返回这个节点。
LeetCode算法题：141. Linked List Cycle
Given a linked list, determine if it has a cycle in it.
public boolean hasCycle(ListNode head) {
if(head == null) {
return false;
}
// two pointer strategy
ListNode p1 = head;
ListNode p2 = head;
while(p2 != null && p2.next != null) {
p1 = p1.next;
p2 = p2.next.next;
if(p1 == p2) {
return true;
}
}
return false;
}
LeetCode算法题：142. Linked List Cycle II
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
public ListNode detectCycle(ListNode head) {
if(head == null || head.next == null) {
return null;
}
// two pointer strategy
ListNode p1 = head;
ListNode p2 = head;
while(p2 != null && p2.next != null) {
p1 = p1.next;
p2 = p2.next.next;
if(p1 == p2) {
break;
}
}
if(p1 != p2) {
return null;
}
ListNode p = head;
while(p != p2) {
p = p.next;
p2 = p2.next;
}
return p;
}
LeetCode算法题：287. Find the Duplicate Number
Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
public int findDuplicate(int[] nums) {
/*
假设数组长度为5，则元素范围是 1~4
*/
int n = nums.length;
// Sorting algorithm: O(N*logN)
/*
Arrays.sort(nums);
int result = nums[0];
for(int i = 1; i < nums.length; i++) {
if(result == nums[i]) {
return result;
}
else {
result = nums[i];
}
}
return 0;*/
// Floyd's Tortoise and Hare 链表闭环判断算法
/*
定义两个指针 p1，p2，根据当前的值向前跳动。
由于数组中肯定有重复的元素，因此 p1 和 p2 肯定会相遇。
*/
int p1 = nums[0];
int p2 = nums[0];
while(true) {
p1 = nums[nums[p1]];
p2 = nums[p2];
if(p1 == p2) {
break;
}
}
int p = nums[0];
while(p != p2) {
p = nums[p];
p2 = nums[p2];
}
return p;
}
