环形链表

141. 环形链表

141. 环形链表

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null||head.next==null) return false;
        ListNode slow=head.next;
        ListNode fast=head.next.next;
        while(slow!=fast){
            if(fast==null||fast.next==null) return false;
            slow=slow.next;
            fast=fast.next.next;
        }
        return true;
    }
}

142. 环形链表 II

142. 环形链表 II
假设环路开始的节点索引为a，循环的长度为loop（loop步，不是loop个节点）
第一阶段：
fast一次走2步，slow一次走1步
fast和slow相遇的时候，一定都在循环里，fast可能已经走了N遍循环了，假设slow走到循环起点后走了x步相遇
2(a+x)=a+x+Nloop
可以得到x+a=Nloop
此时slow再走a步就可以走完循环回到循环的起点，如何得到a？
第二阶段：
把fast放回head一步一步走，走a步便会和slow在循环的起点相遇
最后结果返回循环的起点

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null||head.next==null) return null;
        ListNode slow=head.next;
        ListNode fast=head.next.next;
        while(slow!=fast){
            if(fast==null||fast.next==null) return null;
            slow=slow.next;
            fast=fast.next.next;
        }
        fast=head;
        while(slow!=fast){
            slow=slow.next;
            fast=fast.next;
        }
        return fast;
    }
}

287. 寻找重复数

287. 寻找重复数
与环形链表II思路相同
题目：给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。
可以知道对于数组中任意一个数num，nums[num]都没有越界，都有对应的值。
输入数组：nums = [1,3,4,2,2]
有两个2，nums[3]=2，nums[4]=2，节点3和节点4都指向2这个节点。

把数组看成一个链表，起点head=0，head.next=nums[0]
输入的数组可以形成一个环形链路，需要找到的重复数就是环路的起点。

class Solution {
    public int findDuplicate(int[] nums) {
        int fast=nums[nums[0]];
        int slow=nums[0];
        while(fast!=slow){
            fast=nums[nums[fast]];
            slow=nums[slow];
        }
        fast=0;
        while(fast!=slow){
            fast=nums[fast];
            slow=nums[slow];
        }
        return slow;
    }
}