在单链表中查找循环，而不使用慢指针和快指针

Question

我们知道，为了检测链表中的循环，我们使用慢指针和快指针，首先用头节点初始化两个节点慢和快，然后向前两步遍历快指针，向前一步遍历慢指针
如果我们发现两个地址相等，那么如果fast==null | | fast，则存在循环。next==null则不存在循环

现在我的问题是
是否有可能在不使用快速和慢速指针的情况下检测单链表中的循环

任何想法将不胜感激。
提前感谢。

Answer 1

当然可以。最直观的方法是遍历每个节点并检查您是否访问过该节点。如果您之前访问过此节点，这意味着存在一个循环，并且此特定节点是循环的开始。

要检查您是否早些时候访问过这个节点，您可以维护一个哈希集，它允许您以O（1）时间复杂度检查元素的存在。检查下面的伪代码。

时间复杂度-O（n）

空间复杂度-O（n）

boolean isCyclic(Node head){
  HashSet<Node> set = new HashSet<Node>();    
  while(head != NULL){
    if(set.contains(head))
       return true;
    set.add(head)
    head = head.next  
  }
  return false;
}

Answer 2

至少还有另外两种解决方案。

O（n^2）解决方案是跟踪节点编号。在每个节点上，返回头部并计算到达当前节点所需的next操作数。如果在执行nnext操作之前到达第n个节点，则列表中有一个循环。即:

// assuming head is not null, and head doesn't point to itself
nodeNumber = 1
current = head.next
while (current != null)
{
    p = head
    counter = 0
    while (p != current && counter < nodeNumber)
    {
        p = p.next
        counter = counter + 1
    }
    if (p != current)
        there's a loop
    nodeNumber = nodeNumber + 1
}

一种破坏性的方法是在运行时反转链接。如果链表中有一个循环，那么当指针等于null时，它将位于根。即:

if (head == null) || (head.next == null)
    no loop

prev = head
current = head.next
while (current != null)
{
    // save next position
    next = current.next
    // reverse the link
    current.next = prev
    // and move to the next node
    prev = current
    current = next
}
if (prev == head)
    there is a loop

这样做的缺点是，如果列表中有循环，则会将其销毁。如果没有循环，可以返回列表并反转链接。