如何确定一个链表是否只有一个循环使用两个内存位置

有没有人知道一个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; } } }