如何确定是否一个链表有仅使用两个存储单元一个周期 [英] How to determine if a linked list has a cycle using only two memory locations

问题描述

有谁知道一个算法来寻找，如果一个链表只用两个变量来遍历列表自身循环。假设你有对象的链表，无所谓什么类型的对象。我有一个指向该链接的表中一个变量的头部与我只给定的一个遍历该列表与其他变量。

Does anyone know of an algorithm to find if a linked list loops on itself using only two variables to traverse the list. Say you have a linked list of objects, it doesn't matter what type of object. I have a pointer to the head of the linked list in one variable and I am only given one other variable to traverse the list with.

所以，我的计划是比较指针值，看是否有三分球都是一样的。该列表是有限大小的，但可能是巨大的。我既可以变量设置为头部，然后遍历列表与另一个变量，总是检查，如果它等于另一个变量，但是，如果我打了一个循环，我将永远不能摆脱它。我想它必须与遍历列表和比较指针值的不同速率。有什么想法？

So my plan is to compare pointer values to see if any pointers are the same. The list is of finite size but may be huge. I can set both variable to the head and then traverse the list with the other variable, always checking if it is equal to the other variable, but, if I do hit a loop I will never get out of it. I'm thinking it has to do with different rates of traversing the list and comparing pointer values. Any thoughts?

推荐答案

我会建议使用弗洛伊德的循环查找算法的又名的的龟兔赛跑算法。它有O（n）的复杂性，我认为它符合您的要求。

I would suggest using Floyd's Cycle-Finding Algorithm aka The Tortoise and the Hare Algorithm. It has O(n) complexity and I think it fits your requirements.

例如code：

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;
}

在维基百科更多信息：弗洛伊德的循环查找算法

More info on Wikipedia: Floyd's cycle-finding algorithm.

这篇关于如何确定是否一个链表有仅使用两个存储单元一个周期的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！