今天主要做了这两道题
链表中环的入口结点_牛客题霸_牛客网 (nowcoder.com)、
287. 寻找重复数 - 力扣（LeetCode） (leetcode-cn.com)
1.链表中环的入口节点
描述
给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。
数据范围：?n\le10000n≤10000，1<=结点值<=100001<=结点值<=10000
要求：空间复杂度?O(1)O(1)，时间复杂度?O(n)O(n)
例如，输入{1,2},{3,4,5}时，对应的环形链表如下图所示：
可以看到环的入口结点的结点值为3，所以返回结点值为3的结点。
思路如下
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead) {
if(pHead == null) return null;
ListNode slow=pHead;
ListNode fast=pHead;
while(fast!=null&&fast.next!=null){
slow=slow.next;
fast=fast.next.next;
if(fast==slow) break;
}
if(fast==null||fast.next==null) return null;
slow=pHead;
while(slow!=fast){
slow=slow.next;
fast=fast.next;
}
return slow;
}
}
2.寻找重复数
给定一个包含?n + 1 个整数的数组?nums ，其数字都在 1 到 n?之间（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。
你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。
示例 1：
输入：nums = [1,3,4,2,2]
输出：2
示例 2：
输入：nums = [3,1,3,4,2]
输出：3
示例 3：
输入：nums = [1,1]
输出：1
示例 4：
输入：ums = [1,1,2]
输出：1
我的思路，先排序，然后找到两两相同。或者直接用Hash表统计数量，但与题目要求相冲突。
后根据大神解题思路，巧用快慢指针求解。
class Solution {
public int findDuplicate(int[] nums) {
int slow = 0, fast = 0;
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
slow = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
}
思路如下
快慢指针思想, fast 和 slow 是指针, nums[slow] 表示取指针对应的元素
注意 nums 数组中的数字都是在 1 到 n 之间的(在数组中进行游走不会越界),
因为有重复数字的出现, 所以这个游走必然是成环的, 环的入口就是重复的元素,
即按照寻找链表环入口的思路来做