求第一个入环的点

发表于 分类于 阅读次数： 本文字数： 1.6k 阅读时长 ≈ 3 分钟

基本思路

  1. 开始时快指针走两步，慢指针走一步
  2. 如果相遇，则找到第一个相遇的点
  3. 快指针回到头结点，慢指针原地不动
  4. 快慢指针各走一步，这时再相遇的点就是入环节点

链表类型例题

LCR 022. 环形链表 II

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

第一种方法，不考虑题目中限定的解决方案条件，可以使用hash_set记录遍历过的节点，如果再次遍历到该节点，说明成环且该节点就是入环的节点。

第二种方法，采用我们之前提到的思路，可以省去额外的空间，且空间复杂度为O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (!head || !head->next || !head->next->next) {
            return nullptr;
        }
        ListNode* slow = head->next;
        ListNode* fast = head->next->next;
        while (fast != slow) {
            if (!fast->next || !fast->next->next) {
                return nullptr;
            }
            fast = fast->next->next;
            slow = slow->next;
        }
        fast = head;
        while (fast != slow) {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

数组类型例题

287. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

如果我们根据数组的元素进行坐标跳转，会发现一个规律，最后这个跳转的过程会形成一个环，而入环的节点，就是这个重复的数。

因此，我们可以依照之前提到的流程，进行解答。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) {
            return 0;
        }
        int slow = nums[0];
        int fast = nums[nums[0]];
        // 找到第一个相遇的点
        while (fast != slow) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        // fast回到头结点，slow待在原地
        fast = 0;
        // 每次各跳一步，直到相遇，此时相遇的点就是入环的点
        while (fast != slow) {
            fast = nums[fast];
            slow = nums[slow];
        }
        return slow;
    }
};