快慢指针算法（c++版）

不要秃头不要秃头不要秃头

1157人浏览 · 2025-02-18 15:20:59

不要秃头不要秃头不要秃头 · 2025-02-18 15:20:59 发布

跟双指针可不一样，快慢指针算法是用来检测链表结构是否存在循环的。

方法：初始化两个指针，一个每次移动一步（慢指针），另一个每次移动两步（快指针）。如果存在循环，快指针最终会与慢指针相遇。如果快指针到达链表末尾，则不存在循环。

【leetcode 141】环形链表

给你一个链表的头节点 head ，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ，则返回 true 。否则，返回 false 。

思路与分析：结合这个图片，我们可知道，用哈希表可以记录下来。若当前节点已经在表中了，那就存在环，没在就加入表。所以要么检测到重复节点，即成环；要么到最后也内有检测到重复节点就结束了，不成环。

unordered_set<ListNode*> seen;

for(ListNode*p=head;p!=nullptr;p=p->next) { // C++11 标准起，更推荐使用 nullptr 来表示空指针，而不是 NULL。nullptr 具有更好的类型安全性

if(seen.count(p)) return true; //count()用于检测表中是否含有某元素，有返回1，无返回0

seen.insert(p);//没有就插入

}

return false;

用一个指针在遍历的时候会一直不停止，无法进行确定性的判断。若用一对快慢指针，若存在环形，那么快指针先入环，后面等慢指针也入环了，就会出现一个神奇的现象，因为两指针速度不同，最后一定会相遇；没环的话，不会相遇。so可以用两指针最终会不会相遇（相等），来作为链表中是否有环的判断。

算法与代码：我们规定一下慢指针速度是1，快指针速度是2。也就是分别以 s->next和 f->next->next 两种变化量进行更新。

#include <iostream>
using namespace std;

// 定义链表节点
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 判断链表是否有环的函数
bool isCircle(ListNode* head) {
    if (!head || !head->next) return false;

    ListNode* slow = head;
    ListNode* fast = head->next;

    while (fast && fast->next) {
        if (fast == slow) return true;
        fast = fast->next->next;
        slow = slow->next;
    }

    return false;
}

int main() {
    // 创建链表节点
    ListNode* node1 = new ListNode(1);
    ListNode* node2 = new ListNode(2);
    ListNode* node3 = new ListNode(3);
    ListNode* node4 = new ListNode(4);

    // 构建无环链表：1 -> 2 -> 3 -> 4
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;

    cout << "无环链表测试结果: " << isCircle(node1) << endl;  // 输出 0

    // 构建有环链表：1 -> 2 -> 3 -> 4 -> 2
    node4->next = node2;

    cout << "有环链表测试结果: " << isCircle(node1) << endl;  // 输出 1

    // 注意：有环链表不能用 delete 正常释放，会造成死循环
    return 0;
}

【leetcode 202】快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是快乐数就返回 true ；不是，则返回 false 。

思考与分析：

“对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。”这个描述的算法是这样子

do{//这是某一次的平方和计算

a1=a%10;

sum+=a1*a1;

}while(a/=10)

“然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1”。这句话看起来貌似很费解，什么时候知道这个数变为1呢，生成的结果那么随机又不确定？哎，我们发现一个事情哦，就是若一个数的范围是[1,9]那么各个数位上数字平方和就是[1,81]; [10,99]——[1,162]；[100,999]——[1,243];[1000,9999]——[1,324].....可以发现即使数字很大，它各个数位上的平方和也不是很大呢，再看一下我们还能发现，计算平方和在迭代的时候下降的很快，有点儿收敛的意思吧，具体就是在区间[1,243]之间取值。比如，我们取 n=1234 ,其各位平方和是30,继续算就是9，继续算就是81-->65-->61.......也就是说每次的计算结果会收敛在一个比较小的范围内。那么，在计算次数够多，范围又确定的情况下，可能会出现重复的值。比如 4-->16-->37-->58-->89-->145-->42-->20-->4，也就是说若在计算平方和的时候某一区间内的值被取了两次，那就是循环了。好好好，既然是有区间内的循环，就是成了一个闭环了，采用快慢指针算法。（我们在计算的时候还发现了56和65在计算各位平方和的结果是一样的，可以继续优化，如加一个对称数机制或者其他）

#include <iostream>
using namespace std;

// 计算一个数各位数字的平方和
int bitSquareSum(int a) {
    int sum = 0;
    do {
        int a1 = a % 10;
        sum += a1 * a1;
        a /= 10;
    } while (a > 0);
    return sum;
}

// 判断是否是快乐数（使用快慢指针）
bool isHappy(int n) {
    int slow = n, fast = n;
    do {
        slow = bitSquareSum(slow);
        fast = bitSquareSum(fast);
        fast = bitSquareSum(fast);
    } while (slow != fast);
    return slow == 1;
}

int main() {
    int test_cases[] = {19, 2, 7, 1}; // 示例测试用例
    for (int num : test_cases) {
        bool result = isHappy(num);
        cout << num << ": " << (result ? "true" : "false") << endl;
    }
    return 0;
}

【leetcode 287】寻找重复数给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。【4,2,5,7,3,6,1,8,6】

1.假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

思考与分析：1.用哈希表存储，把每个数字出现就记录一下，但是耗空间也比较耗时间，尤其是在进行查找的时候。 2.先排序，再遍历比较前后元素是否相等，但是题目要求不能改变数组的位序，额外空间也规定了O(1)。3.快慢双指针

很官方的解题思路：用链表的方法，将数组转换成链表的形式来进行计算。用链表可以很好地分析环形结构。又因为题目中索引范围 i 取值是[0,n] ，元素范围[1,n]，所以可以用 num[i]—>num[num[i]]来进行连接每个元素，即当前的值是下一个值的索引（位置或地址），这就形成了一个与原来不一样的序列，4--3--7--8--6(后)--1--2--5--6(前)--1--2....虽然两个6不一样，但6所指向的其他序列都是一样的，即生成了环形。循环体就是1--2--5--6(前)，那么找到循环体之后，在循环体内找到这个重复数字即可，我们发现这个6可以说就在这个环口处，那么如何来确定环口处所在的数字或者是位置就可以得到最终答案。

1.先来找环吧。还是得靠快慢指针

int f = 0, = 0;

do{

f = nums[nums[f]];

s = nums[s];

}while(f!=s)

一个发现：s与f经过n次循环相遇，s走了n， f走了2n, 记原点到环入口距离为m，那么s在环中距离为n-m, 同理，f在环中距离为2n-m,此时有f == s, (2n-m - (n - m) )%c = 0，即 n%c=0 , 循环次数就是环中数字的倍数。那到底f和s现在在哪里，又怎么在环中找重复的数字呢？通过将其中一个指针移到起点，然后以相同速度移动，最终相遇的点就是环的入口，也就是重复的数字。我们要找一些相关数据量呢。

数学推导部分：设非环部分长度为F，环长度为C。相遇时，慢指针走过的步数为 F + a（a为环内相遇点到环入口的距离），快指针步数为 F + a + n*C（n为快指针绕环的圈数）。根据快慢指针速度关系可得：2(F+a)=F+a+n*C⟹ F=n*C−a

将其中一个指针重置到起点，两指针以相同速度（每次一步）前进。当它们再次相遇时，相遇点即为环的入口。从起点出发的指针走F步到达入口时，另一指针从相遇点出发走F = nC - a步，刚好绕环n圈后也到达入口。

OK，算法思想上通了，下面就是代码部分

#include <iostream>
#include <vector>
using namespace std;

// 快慢指针法找数组中重复的数字（要求：数组长度为 n+1，数字范围 1~n）
int findDuplicate(vector<int>& nums) {
    int fast = 0, slow = 0;

    // 第一阶段：进入环，直到相遇
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);

    // 第二阶段：fast 回到起点，再次相遇就是环的入口，即重复数字
    fast = 0;
    while (fast != slow) {
        fast = nums[fast];
        slow = nums[slow];
    }

    return slow;
}

int main() {
    vector<int> nums = {1, 3, 4, 2, 2}; // 示例：重复的是 2
    cout << "重复数字是: " << findDuplicate(nums) << endl;

    return 0;
}