算法-如何仅使用两个内存位置来确定链表是否具有循环

有谁知道一种算法,该算法仅使用两个变量遍历列表就可以找到链表是否在自身上循环。 假设您有一个对象链接列表,那么什么类型的对象都没有关系。 我在一个变量中有一个指向链表头的指针,而我仅获得了另一个变量来遍历链表。

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

jeffD asked 2020-07-20T20:31:34Z
7个解决方案
46 votes

我建议使用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;
}

有关Wikipedia的更多信息:Floyd的循环查找算法。

Baishampayan Ghose answered 2020-07-20T20:31:59Z
17 votes

您可以使用Turtle and Rabbit算法。

维基百科也有一个解释,他们称其为“弗洛伊德的周期发现算法”或“乌龟和野兔”

martinus answered 2020-07-20T20:32:24Z
9 votes

绝对。 实际上,一种解决方案是使用两个指针遍历列表,一个指针的传输速度是另一个指针的两倍。

从指向列表中任何位置的“慢速”和“快速”指针开始。 运行遍历循环。 如果任何时候“快速”指针都与“慢速”指针重合,则您有一个循环链表。

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
}
Frederick The Fool answered 2020-07-20T20:32:48Z
3 votes

我自己尝试解决此问题,并找到了另一种解决方案(效率较低但仍处于最佳状态)。

这个想法是基于线性时间反转单个链表。 这可以通过遍历列表的每个步骤进行两次交换来完成。 如果q是前一个元素(最初为null),而p是当前元素,那么swap(q,p-> next)swap(p,q)将反向链接并同时推进两个指针。 可以使用XOR进行交换,以防止必须使用第三个内存位置。

如果列表中有一个循环,则在迭代过程中的某个时刻,您将到达其指针已更改的节点。 您无法知道是哪个节点,但是通过继续迭代,两次交换一些元素,您将再次到达列表的开头。

通过两次反转清单,清单的结果将保持不变,并且可以根据您是否到达清单的原始头来判断清单是否有周期。

answered 2020-07-20T20:33:22Z
2 votes
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;
}
rajya vardhan answered 2020-07-20T20:33:38Z
1 votes
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;
    }
}
user5297378 answered 2020-07-20T20:33:53Z
0 votes

将这个问题带到下一步将是确定周期(即,不仅存在周期,而且确切地在列表中的位置)。可以使用Tortoise和Hare算法,但是,我们将需要始终跟踪列表的开头。 可以在此处找到该算法的说明。

ND_27 answered 2020-07-20T20:34:14Z
translate from https://stackoverflow.com:/questions/494830/how-to-determine-if-a-linked-list-has-a-cycle-using-only-two-memory-locations