要找到链表中的循环,我们只需使用两个指针慢速和快速即可。
slow = head->next;
fast = head->next->next;
while(slow != fast)
{
slow = head->next;
fast = head->next->next;
if(!slow || !fast)
{
cout<<" No Loop ";
break;
}
}
这样我们就可以找到链表中的循环了。 现在,如果我让慢指针跳2个节点,快跳3个节点,或者慢3个节点,快4个节点,会有什么影响……
我在代码中尝试过这个,但每次都得到正确的结果。 有人可以解释一下吗?另外,我立即想到的另一件事是,我们可以通过某种特定的慢指针和快指针选择进入无限循环,但找不到一个。
最佳答案
Change in number of hopes will only diminish cycle finding process. It wouldn't put you in infinite loop.
节点数要么是奇数,要么是偶数。所以
Case A : For odd number of nodes (3 or 5 nodes for example)
Case B : For even number of nodes (2 or 4nodes for example)
参见测试示例场景:通用解决方案是:GCD(慢速运动,快运动)将是循环内节点在时间上胶体的点。
(偶数,奇数)慢速移动 2,快移动 3:在情况 A 和 B 中都会被捕获。因为在情况 A 中,快速将继续返回到所选节点(每隔三个节点),而慢会交替变化。
(奇数,偶数)慢速移动 3,快移动 4:在情况 A 和 B 中都会被捕获。因为在情况 A 中,快速将继续返回到每四个节点,并在每三个节点处慢速。这样他们应该会在循环中的第 12 个位置上发生碰撞。
(odd, odd)慢移动1,快移动3:在情况A和B中都被捕获。两者的GCD都是3,所以他们应该在即将到来的第三个节点相遇。
(偶,偶)慢移动2,快移动4:在情况A和B中都被捕获。道理相同。
关于c - 如果我们在链表中查找循环时改变慢指针和快指针的跳数会怎样?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24527079/