如何仅使用两个内存位置确定链表是否具有循环 [英] 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?

推荐答案

我建议使用 Floyd's Cycle-Finding Algorithm aka The Tortoise and the Hare Algorithm.它的复杂度为 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.

示例代码:

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 的循环查找算法.

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

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