如何确定链接列表是否只使用两个内存位置进行循环

Question

有没有人知道一个算法来查找链表是否只使用两个变量来遍历列表.假设您有一个链接的对象列表,它与哪种类型的对象无关.我在一个变量中有一个指向链表头部的指针,我只有一个其他变量来遍历列表.

所以我的计划是比较指针值以查看是否有任何指针相同.该列表的大小有限,但可能很大.我可以将两个变量都设置为头部,然后用另一个变量遍历列表,总是检查它是否等于另一个变量,但是,如果我确实打了一个循环,我将永远不会离开它.我认为它与遍历列表和比较指针值的不同速率有关.有什么想法吗？

Answer 1

我建议使用Floyd's Cycle-Finding Algorithm aka The 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的循环查找算法.

Answer 2

您可以使用Turtle和Rabbit算法.

维基百科也有一个解释,他们称之为" 弗洛伊德的循环寻找算法 "或"乌龟和野兔"

Answer 3

绝对.一个解决方案确实可以用两个指针遍历列表,一个以两倍的速率行进.

从"慢"和"快速"指针开始,指向列表中的任何位置.运行遍历循环.如果"快速"指针在任何时候与慢速指针一致,则您有一个循环链表.

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
}