假设您在Java中有一个链表结构。它由节点组成:

class Node {
    Node next;
    // some user data
}

每个节点都指向下一个节点,除了最后一个节点,它的next为空。假设有一种可能性,列表可以包含一个循环-即最后的节点,而不是有一个空值,有一个引用到列表中它之前的一个节点。

最好的写作方式是什么

boolean hasLoop(Node first)

如果给定的节点是带有循环的列表的第一个,则返回true,否则返回false ?你怎么能写出一个常数的空间和合理的时间呢?

下面是一个带有循环的列表的图片:


当前回答

我可能会非常晚和新的处理这个线程。但还是. .

为什么不能将节点的地址和“下一个”节点指向存储在表中

如果我们可以这样做

node present: (present node addr) (next node address)

node 1: addr1: 0x100 addr2: 0x200 ( no present node address till this point had 0x200)
node 2: addr2: 0x200 addr3: 0x300 ( no present node address till this point had 0x300)
node 3: addr3: 0x300 addr4: 0x400 ( no present node address till this point had 0x400)
node 4: addr4: 0x400 addr5: 0x500 ( no present node address till this point had 0x500)
node 5: addr5: 0x500 addr6: 0x600 ( no present node address till this point had 0x600)
node 6: addr6: 0x600 addr4: 0x400 ( ONE present node address till this point had 0x400)

这样就形成了一个循环。

其他回答

这段代码经过优化,将比选择的最佳答案更快地产生结果。这段代码避免了进入一个非常长的追逐向前和向后节点指针的过程,如果我们遵循'最佳答案'方法,在以下情况下将发生这种情况。看一下下面的演练,你就会明白我想说的是什么。然后通过下面给出的方法来观察问题,并测量否。为了找到答案所采取的步骤。

1 - > 2 - > 9 - > 3 ^ -- -- -- -- -- -- -- - ^

代码如下:

boolean loop(node *head)
{
 node *back=head;
 node *front=head;

 while(front && front->next)
 {
  front=front->next->next;
  if(back==front)
  return true;
  else
  back=back->next;
 }
return false
}

我看不出有任何方法可以让这花费固定的时间或空间,两者都会随着列表的大小而增加。

我将使用IdentityHashMap(假设还没有IdentityHashSet)并将每个节点存储到映射中。在存储节点之前,您可以对其调用containsKey。如果节点已经存在,则有一个周期。

ItentityHashMap使用==而不是.equals,这样你就可以检查对象在内存中的位置,而不是它是否具有相同的内容。

下面是检测循环的解决方案。

public boolean hasCycle(ListNode head) {
            ListNode slow =head;
            ListNode fast =head;

            while(fast!=null && fast.next!=null){
                slow = slow.next; // slow pointer only one hop
                fast = fast.next.next; // fast pointer two hops 

                if(slow == fast)    return true; // retrun true if fast meet slow pointer
            }

            return false; // return false if fast pointer stop at end 
        }

我读了一些答案,人们忽略了上述问题的一个明显的解决方案。

如果给定我们可以改变类Node的结构,那么我们可以添加一个布尔标志来知道它是否被访问过。这样我们只遍历列表一次。

Class Node{

 Data data;
 Node next;
 boolean isVisited;

}


public boolean hasLoop(Node head){
   
     if(head == null) return false;

     Node current = head;


     while(current != null){
      if(current.isVisited) return true;
      current.isVisited = true;
      current = current.next;
     }

    return false;

}

这是我在java中的解决方案

boolean detectLoop(Node head){
    Node fastRunner = head;
    Node slowRunner = head;
    while(fastRunner != null && slowRunner !=null && fastRunner.next != null){
        fastRunner = fastRunner.next.next;
        slowRunner = slowRunner.next;
        if(fastRunner == slowRunner){
            return true;
        }
    }
    return false;
}