环形链表(2) ,判断环是否存在,同时找到入口"/>
LeetCode 的 C++ 实现(七)环形链表(2) ,判断环是否存在,同时找到入口
题目
给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
Floyd算法思路
1、通过快慢指针来判断是否存在环
2、
入环前的距离是F,第一次点h,以该点将环分割,两段分别距离分别为a 和 b。
可以得到公式:
2(F + a) = F + N(a + b) + a
2F + 2a = F + 2a + b + (N - 1)(a + b)
F = b + (N - 1)(a + b)
所以可以得出,行进F所耗时间,未走了(N-1)圈环,再走一个b的时间
考虑两个极端情况,如果F的距离远大于环的圆周长,可以想象,N讲无穷大,
当F极短时,则会出现,当h点转完一圈,接近入口是才会第一次相遇,即 N = 1,可得出 F = b;
这时如果一个点从h点出发,一个点从链表头出发,当链表头出发的点走到环入口,那么h点出发的点也会走到环入口(走完N -1圈多走一个b到入口,或者 是另一种F = b情况)
3、讲快头,移位到链表头结点,重新以相同速度出发,当两者再次相遇时,刚好到入口
/*** 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 == nullptr || head->next == nullptr)return nullptr;ListNode* fast = head;ListNode* slow = head;while(fast != nullptr && fast->next != nullptr){fast = fast->next->next;slow = slow->next;if(fast == slow)break;}if(fast == nullptr||fast->next == nullptr)return nullptr;fast = head;while(fast != slow){fast = fast->next;slow = slow->next;}return fast;}
};
哈希表
网上有人写的方法,当然这个方法傻得很,就当复习下set的用法吧
如果我们用一个 Set 保存已经访问过的节点,我们可以遍历整个列表并返回第一个出现重复的节
class Solution {
public:ListNode *detectCycle(ListNode *head) {set<ListNode*> visited;ListNode* p = head;while(p != nullptr){if(visited.count(p) > 0){return p;}visited.insert(p);p = p->next;}return nullptr;}
};
更多推荐
LeetCode 的 C++ 实现(七)环形链表(2) ,判断环是否存在,同时找到入口
发布评论