先来看链表是否有环的判断 设链表起始节点为H，回路起始节点为S，两指针第一次相遇节点为M。 设回路的长度为c，S到M的距离为c1，M到S的距离为c2。 设H到S的距离为d。 设hare每次移动2，tortoise每次移动1。移动k次后两者相遇。不难发现，H到M的距离为k。 为了便于理解，请参考下图：由已知条件，可得到下列等式： hare和tortoise相遇时，hare套了tortoise若干圈。则有： 2k – k = nc = k，n为正整数。 从上图中定义的距离关系，可以得到 c = c1 + c2 k = d + c1 由以上格式变换可得： d = nc – c1 = c2 + (n-1)c 该式具有什么重要意义呢？假设2个指针分别从H和M出发，都是每次移动1的距离，他们会在哪里相遇？ 一个指针从H出发移动d后到达M。另一指针移动 c2 + (n-1)c，(n-1)c意味着绕了n-1圈又回到M，实际上相当于走了c2的距离，到达M。我们发现，两指针必然在S相遇。
代码如下：
public ListNode detectCycle(ListNode head) {
if (head == null) return null;
ListNode fast = head, slow = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
fast = head;
while (fast!=slow){
fast=fast.next;
slow = slow.next;
}
return fast;
}
}
return null;
}
再看一个问题
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.
Note:
- You must not modify the array (assume the array is read only).
- You must use only constant, O(1) extra space.
- Your runtime complexity should be less than
O(n2). - There is only one duplicate number in the array, but it could be repeated more than once.
这个问题的限制条件比较多。不能修改数组元素，只能用常量空间，复杂度<
O(n2).用鸽笼原理很好证明必有重复元素。把元素取值1到n看成n个笼子，n+1个数放到n个笼子必有重复。
举个例子：
4,1,2,3,1
重复的元素构成环
1,2,3,4,5
4,1,2,3,1
1->4, 4->3,3->2,2->1所以1是重复的
int next(int array[], int num) {
return array[num];
}
public int findDuplicate(int[] nums) {
int fast = nums[0], slow = nums[0];
while (true) {
slow = next(nums, slow);
fast = next(nums, next(nums, fast));
if (slow == fast) {
fast = nums[0];
while (fast != slow) {
fast = next(nums, fast);
slow = next(nums, slow);
}
return fast;
}
}
}