【Leetcode】287. 寻找重复数（数组模拟链表的快慢指针法）

寻找重复数

根据题意，数组中的数字都在1~n之间，所以数字的范围是小于数组的范围的，数组的元素可以和数组的索引相联系。

例如：nums[0] = 1 即可以将nums[0]作为索引通过nums[0] 可以访问到nums[1]，以此类推。

如左图所示，环的入口就是重复元素。

那么问题就转化为了如何找到入环的第一个节点的问题。时间复杂度为O(n)

慢指针可以定义为：nums[slow] 快指针可以定义为：nums[nums[fast]]

 class Solution {

     public int findDuplicate(int[] nums) {

         int slow = 0;

         int fast = 0;

         slow = nums[slow];

         fast = nums[nums[fast]];

         while(slow != fast){

             slow = nums[slow];

             fast = nums[nums[fast]];

         }

         fast = 0;

         while(slow != fast){

             fast = nums[fast];

             slow = nums[slow];

         }

         return slow;

     }

 }

【下面顺便复习一下关于链表的题】

环形链表

141. 环形链表

1. 判断是否有环的思路：使用快慢指针。快指针走两步，慢指针走一步，最终快慢指针在环上相遇，且绕圈小于两圈。

 public class Solution {

     public boolean hasCycle(ListNode head) {

         if(head == null || head.next == null || head.next.next == null){

             return false;

         }

         ListNode slow = head.next;

         ListNode fast = head.next.next;

         while(slow != fast){

             if(fast.next == null || fast.next.next == null){

                 return false;

             }

             slow = slow.next;

             fast = fast.next.next;

         }

         return true;

     }

 }

142. 环形链表 II

2. 寻找入环第一个节点：使用快慢指针。快指针走两步，慢指针走一步，一起走到相遇节点后，慢指针不动，快指针回到原点，然后快慢指针再一起一步一步地走，相遇点即入环的第一个节点。

 public class Solution {

     public ListNode detectCycle(ListNode head) {

         if(head == null || head.next == null|| head.next.next == null){

             return null;

         }

         ListNode slow = head.next;

         ListNode fast = head.next.next;

         while(slow!=fast){

             if(fast.next == null || fast.next.next == null){

                 return null;

             }

             slow = slow.next;

             fast = fast.next.next;

         }

         fast = head;

         while(slow != fast){

             slow = slow.next;

             fast = fast.next;

         }

         return slow;

     }

 }

相交链表

3. 找出两个链表相交的第一个节点

两个链表的三种可能情况：

一个有环，一个无环：不可能相交
两个都无环：需要判断是否相交。相交，则是第一个相交节点。不相交，返回null。
两个都有环

两个各自一个环：不相交，返回null
两个共用一个环

先找入环的第一个节点 loop1和loop2
入环节点一样：loop1==loop2 可以转化为无环的相交问题，终止节点变成了loop节点。
入环节点不一样：loop1继续向下走直到遇到loop2，如果没有遇到则是两个各自一个环。返回loop1或loop2。

Leetcode：面试题 02.07. 链表相交

两个都无环相交的情况：

思路：如果两个链表相交，那么末尾的节点一定是同一个，因为一个节点只有一个出度。假设长链表长len1，短链表长len2，长链表先走len1-len2步，短链表从回到起点跟着一起走，相遇点即交点。

 public class Solution {

     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

         ListNode curA = headA;

         ListNode curB = headB;

         int lenA = 0, lenB = 0;

         while(curA != null){

             curA = curA.next;

             lenA ++;

         }

         while(curB != null){

             curB = curB.next;

             lenB ++;

         }

         //A始终是长链表

         curA = lenA > lenB ? headA:headB;

         curB = curA == headA? headB:headA;

         int del = Math.abs(lenA - lenB);

         while(del > 0){

             curA = curA.next;

             del--;

         }

         while(curA!=curB){

             if(curA.next == null || curB.next == null){

                 return null;

             }

             curA = curA.next;

             curB = curB.next;

         }

         return curA;

     }

 }

两个都有环相交的情况：

【待续】

巴特西