如何确定一个链表是否只有一个循环使用两个内存位置
有没有人知道一个algorithm来查找链表是否仅使用两个variables来遍历链表本身。 假设你有一个链接的对象列表，不pipe对象是什么types。 我有一个指针的链接列表中的一个variables的头，我只给了一个其他variables遍历列表。
所以我的计划是比较指针值，看是否有指针是相同的。 名单是有限的大小，但可能是巨大的。 我可以设置两个variables的头部，然后遍历列表与其他variables，总是检查是否等于另一个variables，但是，如果我打了一个循环，我永远不会离开它。 我认为它必须处理不同的遍历列表和比较指针值的速度。 有什么想法吗？
我会build议使用Floyd's Cycle-Finding Algorithm 又名 Tortoise and the Hare Algorithm 。 它具有O（n）的复杂性，我认为它符合你的要求。
示例代码：
function boolean hasLoop(Node startNode){ Node slowNode = Node fastNode1 = Node fastNode2 = startNode; while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){ if (slowNode == fastNode1 || slowNode == fastNode2) return true; slowNode = slowNode.next(); } return false; }
更多的信息在维基百科： Floyd的循环寻找algorithm 。
你可以使用龟和兔子algorithm。
维基百科也有一个解释，他们称之为“ 弗洛伊德的循环发现algorithm ”或“乌龟和兔子”
绝对。 一个解决scheme确实可以用两个指针来遍历列表，一个以两倍于另一个的速度行进。
从“缓慢”和“快速”指针开始，指向列表中的任何位置。 运行遍历循环。 如果任何时候“快速”指针与慢速指针一致，则有一个循环链表。
int *head = list.GetHead(); if (head != null) { int *fastPtr = head; int *slowPtr = head; bool isCircular = true; do { if (fastPtr->Next == null || fastPtr->Next->Next == null) //List end found { isCircular = false; break; } fastPtr = fastPtr->Next->Next; slowPtr = slowPtr->Next; } while (fastPtr != slowPtr); //Do whatever you want with the 'isCircular' flag here }
我试图自己解决这个问题，并find了一个不同的（效率较低但仍是最优的）解决scheme。
这个想法是基于在线性时间倒转一个单独的链表。 这可以通过在迭代列表中的每一步执行两次交换来完成。 如果q是前一个元素（最初为null），而p是当前的，那么swap（q，p-> next）swap（p，q）将反转链接并同时推进两个指针。 交换可以使用XOR来完成，以防止使用第三个存储位置。
如果列表有一个循环，那么在迭代期间的一个点上，你将到达一个指针已经被改变的节点。 你不知道哪个节点是这样的，但是通过继续迭代，交换一些元素两次，你再次到达列表的头部。
通过颠倒列表两次，列表的结果保持不变，您可以根据您是否到达列表的原始头部来判断是否有循环。
int isListCircular(ListNode* head){ if(head==NULL) return 0; ListNode *fast=head, *slow=head; while(fast && fast->next){ if(fast->next->next==slow) return 1; fast=fast->next->next; slow=slow->next; } return 0; }
把这个问题带到下一个步骤就是识别循环（也就是说，不仅仅是循环存在，而是它在列表中的确切位置）。 乌龟和兔子algorithm可以用于相同的，但是，我们将要求始终跟踪列表的头部。 这个algorithm的例子可以在这里find。
boolean findCircular(Node *head) { Node *slower, * faster; slower = head; faster = head->next; while(true) { if( !faster || !faster->next) return false; else if (faster == slower || faster->next == slower) return true; else{ faster = faster->next->next; } } }
