#单链表与环的情况
###1.判断链表是否有环
对于这个问题我们可以采用“快慢指针”的方法。就是有两个指针fast和slow，开始的时候两个指针都指向链表头head，然后在每一步操作中slow向
前走一步即：slow = slow->next，而fast每一步向前两步即：fast = fast->next->next。
由于fast要比slow移动的快，如果有环，fast一定会先进入环，而slow后进入环。当两个指针都进入环之后，经过一定步的操作之后
二者一定能够在环上相遇，并且此时slow还没有绕环一圈，也就是说一定是在slow走完第一圈之前相遇（肯定是在环上进行相遇）。证明可以看下图：
public class Solution {
public boolean hasCycle(ListNode head) {
if(head==null) return false;
ListNode walker = head;
ListNode runner = head;
//主要考虑前面的情况吧
//如果是没有环的情况
while(runner.next!=null && runner.next.next!=null)
{
//如果没有环的话,逐步减少差距，总会在一个地方相遇到的情况
walker = walker.next;
runner= runner.next.next;
if(walker==runner)
return true;
}
//如果是有环的情况
return false;
}
}
###2.判断一个链表是否环，并返回环的开始位置
画一个图即可判断处理， 假设走了K步两者第一次在环上相遇，此时2K-K=R(R代表环的长度)， 所以有K=R假设S代表链表起点到环起点的位置，M代表环起点的位置到第一次相遇的地方, R =K=S+M, 所以S = R-M ，当
所以当runner和walker在第一次相遇的时候，让walker回到起，让walker走S， 让runner走 R-M, 由于s=r-m 两者会在环起点的位置初相遇，
记住runner走了两个环，walker走的路劲是一个环
public class Solution {
public ListNode detectCycle(ListNode head) {
//有环的话必然是两个以上的节点
if(head==null|| head.next==null) return null;
ListNode walker= head, runner = head;
boolean mark = false;
//判断是否有环代码结构
while(runner.next!=null && runner.next.next!=null){
walker = walker.next;
runner= runner.next.next;
if(runner==walker){
//第一次相遇即可退出
mark = true;
break;
}
}
//没有环的情况
if(!mark) return null;
//有环的情况下两者相遇在环上，让runner停留在第一次相遇的地方
walker = head;//(hu)
while(walker!=runner){
walker = walker.next;
runner = runner.next;
}
return walker;
}
}
287. Find the Duplicate Number
一个n+1 的数组中存储的元素为1到n,其中有一个数据是重复出现的，请从中找出重复的那个元素情况
class Solution {
public int findDuplicate(int[] nums) {
Map<Integer,Integer> result =new HashMap<>();
for(int i=0;i<nums.length;i++){
//如果不存在可以key, 直接默认的
result.put(nums[i],result.getOrDefault(nums[i], 0) +1);
}
for(Map.Entry<Integer,Integer> element:result.entrySet())
{
if(element.getValue()>1)
return element.getKey();
}
return 0;
}
}
时间复杂度为o(n),空间复杂度为0(n);
如果题目要求可以修改数组的情况发生
归位处理情况
利用抽屉原理 ,将数据进行划分两部分，所以统计[n/2]的数，如果出现小于等于n/2的数个数超过n/2,[n/2]数中有重复的数，继续通过二分减少搜索范围，这里的时间复杂度为nlogn。改变low或者high这两个变量，缩小查找范围
mid =(low+high)/2;
统计数组中小于等于mid的个数count，如果count>=mid, 证明这边的数据多了一个，high = mid -1;
否则low = mid +1;
代码
class Solution(object):
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
low = 1
high = len(nums)-1
while low < high:
mid = low+(high-low)/2
count = 0
for i in nums:
if i <= mid:
count+=1
if count <= mid:
low = mid+1
else:
high = mid
return low
At first the search space is numbers between 1 to n. Each time I select a number mid (which is the one in the middle) and count all the numbers equal to or less than mid. Then if the count is more than mid, the search space will be [1 mid] otherwise [mid+1 n]. I do this until search space is only one number.
public solution{
public int find(int []nums){
//条件判断就写了
int low = 0;
int high = nums.length-1;
while(low<high)
{
int mid = (low+high)<<2;
int count =0;
for(int i=0;i<nums.length-1;i++){
if(nums[i]<=mid){
count++;
}
}
if(count>mid){
high = mid;
}
else
{
low = mid+1;
}
return low;
}
}
时间复杂度为o(nlog(n))即可