dz网站制作,中国医院建设协会网站,英文网站建设教程,自由贸易试验区网站建设方案1.快慢指针 例题 给定一个链表#xff0c;判断链表中是否有环。
如果链表中有某个节点#xff0c;可以通过连续跟踪 next 指针再次到达#xff0c;则链表中存在环。 为了表示给定链表中的环#xff0c;我们使用整数 pos 来表示链表尾连接到链表中的位置#xff08;索引从…1.快慢指针 例题 给定一个链表判断链表中是否有环。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环我们使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。 如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。
如果链表中存在环则返回 true 。 否则返回 false 。
进阶
你能用 O(1)即常量内存解决此问题吗
示例 1 输入head [3,2,0,-4], pos 1 输出true 解释链表中有一个环其尾部连接到第二个节点。
示例 2 输入head [1,2], pos 0 输出true 解释链表中有一个环其尾部连接到第一个节点。
示例 3 提示 链表中节点的数目范围是 [0, 104] -105 Node.val 105 pos 为 -1 或者链表中的一个 有效索引 。
来源力扣LeetCode 链接https://leetcode-cn.com/problems/linked-list-cycle
2.思路
设置一快一慢指针如果快指针追上慢指针则有环。如果快指针到达链表尾说明无环。 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:bool hasCycle(ListNode *head) {if(headnullptr||head-nextnullptr)return false;ListNode * slow head;ListNode * fast slow-next;while(fast!slow){if(fastnullptr||fast-nextnullptr)return false;slow slow-next;fast fast-next-next;}return true;}
}; 3.相似例题
以下本质为快慢指针
26. 删除有序数组中的重复项 - 力扣LeetCode class Solution {
public:int removeDuplicates(vectorint nums) {if (nums.size() 2)return nums.size();int slow 1;int fast 1;for (fast 1; fast nums.size(); fast){if (nums[fast] ! nums[slow-1]){nums[slow] nums[fast];slow;}}return slow;}
}; class Solution {
public:int MoreThanHalfNum_Solution(vectorint nums) {auto slow nums.begin();auto fast nums.end();int flag 0;for (slow nums.begin(); slow nums.end(); slow){flag 0;for (fast nums.begin(); fast nums.end(); fast){if (*fast *slow){flag;}}if(flag nums.size()/2){return *slow;}}return 0;}
}; 优质文章推荐双指针算法详解快慢指针、对撞指针、滑动窗口_滑动窗口和双指针算法-CSDN博客
