如何确定链表是否包含循环? [英] How to determine whether a linked list contains a loop?

问题描述

可能的重复项:
确定是否链表中没有两个循环指针
如何确定链接列表是否仅使用两个内存位置来循环.
测试链表中是否包含链表的最佳算法循环

Possible Duplicates:
find whether a loop in a linked list without two pointers
How to determine if a linked list has a cycle using only two memory locations.
Best algorithm to test if a linked list has a cycle

在准备工作面试时，我遇到了以下问题:

During a preparation for a job interview, I encountered the following question:

如何使用O(1)的额外空间复杂度来确定(任何类型的)链表是否包含循环?您不能假设循环从第一个节点开始(当然，循环不必包含所有节点).

How can you determine whether a linked list (of any type) contains a loop, using additional space complexity of O(1)? You cannot assume that the loop starts at the first node (and of course, the loop doesn't have to contain all nodes).

我找不到答案，尽管我觉得这很简单...

I couldn't find the answer, though I have the feeling it's quite simple...

推荐答案

简单.保持两个指针到列表中.在每个步骤中，将一个指针前移单个链接，将另一个指针前移两个链接.测试以查看它们是否指向相同的元素.如果是这样，您就有一个循环.如果没有，请重复直到找到一个循环或到达列表的末尾.

Easy. Maintain two pointers into the list. At each step, advance one pointer by a single link, and advance the other by two links. Test to see if they point to the same element. If so, you have a loop. If not, repeat until you find a loop or you reach the end of the list.

这篇关于如何确定链表是否包含循环?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！