根据题意，数组中的数字都在1~n之间，所以数字的范围是小于数组的范围的，数组的元素可以和数组的索引相联系。
例如：nums[0] = 1 即可以将nums[0]作为索引 通过nums[0] 可以访问到nums[1]，以此类推。
如左图所示，环的入口就是重复元素。
那么问题就转化为了如何找到入环的第一个节点的问题。时间复杂度为O(n)
慢指针可以定义为：nums[slow] 快指针可以定义为：nums[nums[fast]]
1 class Solution { 2 public int findDuplicate(int[] nums) { 3 int slow = 0; 4 int fast = 0; 5 slow = nums[slow]; 6 fast = nums[nums[fast]]; 7 while(slow != fast){ 8 slow = nums[slow]; 9 fast = nums[nums[fast]]; 10 } 11 fast = 0; 12 while(slow != fast){ 13 fast = nums[fast]; 14 slow = nums[slow]; 15 } 16 return slow; 17 } 18 }
【下面顺便复习一下关于链表的题】
1 public class Solution { 2 public boolean hasCycle(ListNode head) { 3 if(head == null || head.next == null || head.next.next == null){ 4 return false; 5 } 6 ListNode slow = head.next; 7 ListNode fast = head.next.next; 8 while(slow != fast){ 9 if(fast.next == null || fast.next.next == null){ 10 return false; 11 } 12 slow = slow.next; 13 fast = fast.next.next; 14 } 15 return true; 16 } 17 }
2. 寻找入环第一个节点：使用快慢指针。快指针走两步，慢指针走一步，一起走到相遇节点后，慢指针不动，快指针回到原点，然后快慢指针再一起一步一步地走，相遇点即入环的第一个节点。
1 public class Solution { 2 public ListNode detectCycle(ListNode head) { 3 if(head == null || head.next == null|| head.next.next == null){ 4 return null; 5 } 6 ListNode slow = head.next; 7 ListNode fast = head.next.next; 8 while(slow!=fast){ 9 if(fast.next == null || fast.next.next == null){ 10 return null; 11 } 12 slow = slow.next; 13 fast = fast.next.next; 14 } 15 fast = head; 16 while(slow != fast){ 17 slow = slow.next; 18 fast = fast.next; 19 } 20 return slow; 21 } 22 }
1 public class Solution { 2 public ListNode getIntersectionNode(ListNode headA, ListNode headB) { 3 ListNode curA = headA; 4 ListNode curB = headB; 5 int lenA = 0, lenB = 0; 6 while(curA != null){ 7 curA = curA.next; 8 lenA ++; 9 } 10 while(curB != null){ 11 curB = curB.next; 12 lenB ++; 13 } 14 //A始终是长链表 15 curA = lenA > lenB ? headA:headB; 16 curB = curA == headA? headB:headA; 17 int del = Math.abs(lenA - lenB); 18 while(del > 0){ 19 curA = curA.next; 20 del--; 21 } 22 while(curA!=curB){ 23 if(curA.next == null || curB.next == null){ 24 return null; 25 } 26 curA = curA.next; 27 curB = curB.next; 28 } 29 return curA; 30 } 31 }
两个都有环相交的情况：
【待续】
【Leetcode】287. 寻找重复数（数组模拟链表的快慢指针法）
原文：https://www.cnblogs.com/xdcat/p/12969595.html