【Leetcode】287. 寻找重复数（数组模拟链表的快慢指针法）
2021-01-07 19:30
标签：str tco inf null 入口 问题 一个 联系 abs 根据题意，数组中的数字都在1~n之间，所以数字的范围是小于数组的范围的，数组的元素可以和数组的索引相联系。 例如：nums[0] = 1 即可以将nums[0]作为索引 通过nums[0] 可以访问到nums[1]，以此类推。 如左图所示，环的入口就是重复元素。 那么问题就转化为了如何找到入环的第一个节点的问题。时间复杂度为O(n) 慢指针可以定义为：nums[slow] 快指针可以定义为：nums[nums[fast]] 【下面顺便复习一下关于链表的题】 2. 寻找入环第一个节点：使用快慢指针。快指针走两步，慢指针走一步，一起走到相遇节点后，慢指针不动，快指针回到原点，然后快慢指针再一起一步一步地走，相遇点即入环的第一个节点。 两个都有环相交的情况： 【待续】 【Leetcode】287. 寻找重复数（数组模拟链表的快慢指针法） 标签：str tco inf null 入口 问题 一个 联系 abs 原文地址：https://www.cnblogs.com/xdcat/p/12969595.html寻找重复数
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 }
环形链表
141. 环形链表
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 }
142. 环形链表 II
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 }
上一篇：Java包机制
下一篇：spring-bean 生命周期
文章标题：【Leetcode】287. 寻找重复数（数组模拟链表的快慢指针法）
文章链接：http://soscw.com/index.php/essay/40770.html